# Questions tagged [greedy-algorithms]

An algorithm which at every point makes the locally optimal choice.

30 questions
Filter by
Sorted by
Tagged with
4k views

### Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
• 10.5k
936 views

### Max-Cut algorithm that shouldn't work, unclear why

OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic: Given an undirected graph $G=(V,E)$, ...
• 794
2k views

### Does every greedy algorithm have matroid structure?

It is well established that for every matroid $M$ and any weight function $w$, there exits an algorithm $\mbox{GreedyBasis}(M,w)$ which returns a maximum weight basis of $M$. So, is the reverse ...
2k views

### What greedy algorithm satisfies greedy choice property but does not have optimal substructure?

Based on the textbook Introduction to Algorithms, the correctness of a greedy algorithm requires a problem to have two properties: greedy choice property optimal substructure It is easy to come up ...
• 143
507 views

### Why is the Greedy Conjecture so difficult?

I recently learned about the Greedy conjecture for the Shortest Superstring Problem. In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ ...
• 455
358 views

### How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
• 6,605
866 views

### Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?

Greedy is a non-formal term, but it could be (not sure, that's why I'm asking) that for certain problems, greediness can be mathematically formulated and thus be proven that no optimal greedy ...
• 243
420 views

I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \... • 634 5 votes 0 answers 77 views ### reference request: greedy algorithm for fractional interval covering Reference Request I've found a natural greedy algorithm for the problem below. My question is: what is already known about fast algorithms for this problem (faster than general linear programming, ... • 8,133 5 votes 0 answers 175 views ### Which well-known algorithmic problem is this an instance of? Consider that you have n counters initialised with numbers$M_1 \dots M_n$. In each round you decrement exactly$k$out of these counters. Keep doing this until at least$n-k+1$counters are zero, so ... 4 votes 2 answers 209 views ### Maximum Vertex Cover I recently encountered the following exam problem: Given an undirected graph$G := (V,E)$and a natural number$k \geq 1$, we want to cover as many edges as possible using exactly$k$vertices. ... 4 votes 0 answers 167 views ### Simulate a heap in linear time Is there anything in the literature on the following problem?: Take a sequence of operations of Insert(element) and PopMin and ... • 41 3 votes 3 answers 5k views ### Complexity of greedy coloring I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale They describe the Greedy algorithm as follows: ... • 249 3 votes 1 answer 276 views ### Is this greedy algorithm for vertex cover studied before? For the vertex cover problem (Given a graph$G$, find a minimum set$S$of vertices such that$G - S$is edgeless), there are two famous greedy algorithms. The edge greedy (finding an edge and taking ... • 2,530 3 votes 2 answers 579 views ### Follow-the-leader algorithm in swarm formation: literature on the subject? In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum ... 3 votes 1 answer 402 views ### What is the reverse of greedy algorithm for setcover? A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, ... 3 votes 1 answer 198 views ### Interval partitioning with restrictions: NP-complete or efficiently solvable? The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. ... 2 votes 1 answer 565 views ### Huffman Tree Depth, Is there any theory? I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ... 2 votes 0 answers 80 views ### Does the awards budget cut problem support a sub$O(n\log n)$time solution? There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem. The problem gives you an input of$n$integers called grants$g_1 ... ...
1 vote
The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...