Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
2k views

Vertex cover algorithms for directed graphs?

I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph. Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a ...
2
votes
1answer
114 views

Selecting optimal order of questions to minimize total time

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ...
2
votes
2answers
3k views

Minimum difference between two subsets of an array of integers

The Problem Suppose we have an array A[1...n] of integers, with values ranging from 0 to K (so 0<=A[i]<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {...
2
votes
1answer
677 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 ...
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 ...
0
votes
1answer
62 views

How can i fill shelves with products so that I have the maximum amount of sales?

I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales ...
2
votes
3answers
918 views

Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm

The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as ...
1
vote
1answer
1k views

Does a greedy strategy exist for this instance of the Bin Packing Problem?

I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 ...
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
1answer
619 views

Running time of greedy scheduling algorithm

Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum. Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$....
2
votes
2answers
2k 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 ...
1
vote
0answers
385 views

Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is ...
0
votes
1answer
195 views

Cards shuffling. Greedy algorithm

We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck. My idea is to create a priority queue. ...
0
votes
1answer
187 views

Unusual elevator algorithm

An elevator with a capacity of N people in a building with E floors works in a pretty unusual way. The elevator starts at the first floor and it goes to the top floor before returning to the first ...
3
votes
1answer
5k 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 ...
0
votes
0answers
387 views

Interval scheduling, unclear greedy proof

I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem. The proof that I am ...
0
votes
2answers
4k views

Dynamic Programming vs Greedy - coin change problem

This is a fairly common problem: Given coins of integer denominations $v_1 < v_2< ... < v_n$, make change for an amount A using as few coins as possible. Given an input of powers of $p$, ...
0
votes
1answer
217 views

Question regarding coin change algorithm (DP and greedy)

The question goes something like this: Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy ...
1
vote
2answers
1k views

How to prove greedy algorithm for number partitioning?

the partition problem (or number partitioning1) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the ...
2
votes
0answers
2k views

Why is it necessary to sort according to the starting time in the interval partitioning problem?

What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample ? Note- (refer here for detailed definition) ...
0
votes
1answer
324 views

What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?

On Codeforces, the first problem that comes up for the tag "greedy" is "50A: Domino Piling". Here is the problem: You are given a rectangular board of M × N squares. Also you are given an unlimited ...
1
vote
0answers
190 views

Information gain vs Gini impurity, for Random Forest?

I was researching about the supervised algorithm called Random Forest, that made me begin to study about decision trees, and how to induce them from a set, in order to create several predictors. My ...
2
votes
1answer
522 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 ...
4
votes
1answer
500 views

Finding a maximum-weight base of a a matroid, in reverse

Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm: Start with an empty set (by definition of matroid, it is independent). Add ...
3
votes
2answers
1k views

set with maximum sum consisting of mutually co-prime numbers

Definitions. Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and mutually co-prime. Then find the maximum sum the set $S$ can have. Example. Let $n=10$, ...
0
votes
1answer
70 views

Discrete optimisation in 5 variables

I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, ...
0
votes
0answers
71 views

Planning interviews

This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps). Problem is: Everyday I am receiving job offers, and I have to ...
0
votes
0answers
190 views

Greedy algorithm correctness proof (UVA 10716)

Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols (UVA ...
36
votes
2answers
34k views

How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
0
votes
0answers
56 views

How can I divide a set of strings into subsets of fixed size with maximal homogeneity?

Suppose I have a set of 1000 binary strings of fixed length. I wish to divide these 1000 strings into 10 subsets of 100 strings each, in such a way that the subsets are maximally homogeneous. I want ...
2
votes
1answer
151 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 ...
3
votes
1answer
398 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 ...
0
votes
2answers
266 views

Minimizing the overall cost over groups

I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this: ...
0
votes
1answer
605 views

Please check my Huffman tree [closed]

My professor gave an example of Huffman tree. Given inputs a 80 b 10 c 20 d 50 e 100 f 35 g 60 … then the tree will be: But when i tried to solve it at home, I ...
4
votes
1answer
294 views

An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

Suppose there is an unlimited number of pipes, each has length $x$ meters. There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given. For example ...
5
votes
2answers
311 views

Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
-1
votes
1answer
68 views

Optimal way to join pieces when the cost of joining two pieces is $|x-y|$

There are $N$ pieces each having size $A_i$. The cost of joining a piece of size $x$ and a piece of size $y$ is $|x-y|$. What is the most optimal way to join all the pieces? Can it be solved using the ...
2
votes
1answer
3k views

A greedy approximation algorithm for max k-cut

The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$ so that the total cost of edges running ...
1
vote
1answer
88 views

Information about ε-greedy algorithms

I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms ...
7
votes
1answer
3k views

Greedy strategy for computing the minimum number of rays that hit all balloons

The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm". The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the ...
2
votes
0answers
149 views

Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
0
votes
0answers
54 views

Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...
3
votes
4answers
3k views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
2
votes
1answer
836 views

Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
1
vote
0answers
140 views

find max k sequence - is it greedy?

The original problem statement is: Given a sequence of numbers $A[1..n]$, find $k < n$ consecutive numbers such that the sum of these $k$ numbers is maximized where $k$ is a positive ...
5
votes
2answers
1k views

Counterexample to this modified Dijkstra's

In class, we were given the following problem: We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v) which is a real number in the range 0 ≤ r(u, ...
1
vote
5answers
573 views

Correctness of the greedy algorithm

I am trying to solve the following problem: Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of ...
2
votes
3answers
709 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 ...
3
votes
2answers
717 views

Is greedy algorithm the best algorithm for set cover problem?

Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem. I am a bit confused by this theorem. As we know, greedy algorithm is $(\ln n+...
5
votes
1answer
546 views

Variations of Greedy Algorithm

What is the definition of an "orthogonal greedy algorithm"? What is the definition of a "relaxed greedy algorithms"? Can you give an example to illustrate how these notions differ from ordinary ...

1
3 4
5
6 7