# 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 ...
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)$, ...
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 ...
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$ ...
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 ...
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 ...
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 = \... 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, ... 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 ... 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: ... 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 ... 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 ...