Questions tagged [greedy-algorithms]

Questions about algorithms that make at each step the locally optimal choice.

Filter by
Sorted by
Tagged with
3
votes
1answer
192 views

Using a greedy algorithm to find a cut S which at least half of the edges cut

Let $G$ be an undirected graph. Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut. I tried to think about something like choosing the vertex with the highest degree, ...
3
votes
1answer
98 views

Optimal solution for Weighted points problem

Problem: Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, ...
3
votes
1answer
192 views

Greedy Heuristics with an Altered Subset Sum/Partition Problem

Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, ...
3
votes
2answers
2k views

Split array into contiguous subarrays of approximately same sums

My question is similar to this splitting question, but my objective function is different. Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty ...
3
votes
2answers
526 views

Merging balls interview problem

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks. You are given $n$ balls on the table and all the balls are rolling towards the ...
3
votes
1answer
635 views

Correctness proof for greedy algorithm based on ratio

I've an issue stated as follows: We have 10000 jobs to do, each with some length $l_i$ and weight (importance) $w_i$. Our goal is to arrange the schedule of doing these jobs (in other words, ...
3
votes
1answer
415 views

In Data Mining, what does it mean to be greedy?

I am looking at a number of algorithms in Data Mining and some are described as being greedy. My issue is that they seem to be using the term greedy in different ways, which seems contradictory. For ...
3
votes
4answers
3k views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
3
votes
1answer
183 views

Greedy algorithm proof

There are 2n product and their prices: P={p_1, p_2, ..., p_2n}. When we buy the products in pairs we get the product with lower ...
3
votes
1answer
254 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
3
votes
1answer
138 views

Show that approximation ratio for a convex hull algorithm is $\pi/2$

Facts: n points in the plane, each has one of k colors, all k colors are represented. Problem: You wish to select k points, one of each color, such that the perimeter of the convex hull is as small ...
3
votes
1answer
115 views

Greedy algorithm for subset sum on powers of 2

I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after ...
3
votes
1answer
568 views

Hitting Set Problem with non-minimal Greedy Algorithm

The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
3
votes
1answer
522 views

Length of shortest codeword in Huffman encoding

Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1? I thought of 2 cases where this ...
3
votes
1answer
105 views

Globally-optimized nearest neighbors lookup

I have a set $\mathcal{A}$ of $\mathcal{m}$ vectors in $\mathbb{R}^a$. I also have a different set $\mathcal{B}$ of $\mathcal{n}$ vectors in $\mathbb{R}^a$. These two sets are disjoint: $\mathcal{A}\...
3
votes
1answer
6k views

How does “Greedy Stays Ahead” Prove an Optimal Greedy Algorithm?

I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem. On the second page of Cornell's Greedy Stays ...
3
votes
1answer
2k views

Relation between the “Point-Cover-Interval” problem and the “Interval Scheduling” problem

Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains some ...
3
votes
1answer
804 views

Find the minimum set of intervals for given set of numbers

For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$ the answer is $${\{[1....
3
votes
1answer
1k views

How to prove a greedy algorithm that uses the longest increasing subsequence?

Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...
3
votes
1answer
1k views

Easiest improvement on first-fit for bin packing algorithm

See the interactive example here. First-fit on the left, optimal on the right. I know that in general, optimal bin-packing is NP-hard, so I'm not looking for a perfect solution. I'm looking for the ...
3
votes
1answer
2k views

Fast algorithm for matrix chain multiplication in special case

An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots \...
3
votes
1answer
148 views

Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper

Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization ...
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
3
votes
0answers
245 views

Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
2
votes
2answers
2k views

Why this greedy algorithm fails in rod cutting problem?

Recall the rod cutting problem. Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and ...
2
votes
2answers
3k views

Greedy Optimum Dominating Set For A Tree

I am trying to figure out a greedy algorithm that finds the optimum (minimum) dominating set for any tree in linear time. So a greedy algorithm to find a dominating set for a general graph is not ...
2
votes
1answer
403 views

N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its ...
2
votes
1answer
488 views

Gas Station problem : Fixed path variation

Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path ...
2
votes
3answers
4k views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
2
votes
1answer
703 views

Gas Station Problem - Dijkstra's Algorithm variation

I am trying to find an algorithm which finds the least expensive route from one town to another. This is the general setup. There are a series of one-way roads from some towns to other towns. Not ...
2
votes
2answers
708 views

Knapsack with a fixed number of weights

Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There ...
2
votes
2answers
297 views

Shortest travelling cost if we have bunch of points in 2D plane

I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
2
votes
1answer
712 views

How is Dijkstra's algorithm related to breadth first search(BFS)?

I've read in Introduction to algorithms(CLRS) that Dijkstra's algorithm uses ideas similar to those of BFS? I think it really makes sense with respect to Dijkstra's algorithm with relationship to BFS ...
2
votes
1answer
152 views

Proof for This Greedy Strategy for Equalizing An Array

Recently the following problem was posed in a private coding competition at my workplace: An array $A$ is given that has only positive integers in it. The objective is to equalize the array in ...
2
votes
1answer
161 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
2
votes
1answer
24 views

Optimize stacking time series by offsetting start times (feels like a backpack problem?)

Given a time-series of data collected from a single running process that takes 8 hours to complete: Minute GB of Disk Space Used 0 0 1 8 2 15 3 22 ...Etc. It is sampled every minute, for 8 ...
2
votes
1answer
43 views

k-center problem: proof for Gon algorithm gives a 2-approximation

The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following ...
2
votes
1answer
135 views

Proof of a greedy algorithm used for a variation of bin-packing problem

We are given an array of weights $W$ (all weights are positive integers), and we need to put the weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The ...
2
votes
1answer
53 views

Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is ...
2
votes
3answers
810 views

Selecting items from two arrays without duplicate indices to get maximum sum

Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you ...
2
votes
1answer
245 views

Greedy Solution for Selecting Prefix Sum

Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to ...
2
votes
4answers
2k views

A greedy algorithm for the bottle filling problem

(There’s no need to write the algorithm, I just need help with the greedy choice). Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We ...
2
votes
1answer
737 views

Solving “coin exchange” for coins of power values by greedy algorithm

When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$? For ...
2
votes
1answer
233 views

Mimimum spanning tree with a constraint on number of certain types of edges

I have the the following problem. Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
2
votes
1answer
158 views

Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?

The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So ...
2
votes
2answers
86 views

Optimal Partition of Book Chapters

Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions: by the end of each day, you ...
2
votes
1answer
4k views

Where we Use Dynamic Programming and Greedy Algorithm? [closed]

Can someone tell me where we use Dynamic/Greedy algorithm and how we trace from the question that it will solved by any one of the above? Thanks
2
votes
2answers
3k views

Find minimum number of time points that cross out all intervals

Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of ...
2
votes
1answer
557 views

Greedy algorithm for a variation of the $k$-center problem

This is a variation of the well-known $k$-center problem with priorities given on the vertices. Problem: Let $G = (V,E)$ be a complete graph with a distances on the edges satisfying the triangle ...
2
votes
3answers
741 views

Coin Change Problem(Greedy Algorithm)

In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm? Example- $(1,3,4)$ are denominations of coin. If I want to pay ...

1
2
3 4 5
7