Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
4 votes
0 answers
57 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how ...
orlp's user avatar
  • 885
3 votes
1 answer
315 views

How do you achieve linear time complexity of greedy graph coloring?

In most resources I could find, greedy algorithm is described as follows: for every vertex $v$, assign the minimal color not used by its neighbors. The above could be implemented as: ...
Sebastian Szczepański's user avatar
4 votes
2 answers
257 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. ...
reservoir's user avatar
2 votes
0 answers
108 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 ... ...
Sidharth Ghoshal's user avatar
-2 votes
1 answer
72 views

Finding a greedy ordering criteria

I've been thinking through a problem, and I won't go into all the details here but I'm stumped on a particular subproblem: Consider this following definition of a task: $T_k = (a_k, b_k)$. $a_k$ is ...
Chip Bell's user avatar
5 votes
0 answers
98 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, ...
Neal Young's user avatar
  • 10.8k
3 votes
1 answer
330 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. ...
Theemathas Chirananthavat's user avatar
1 vote
0 answers
92 views

Are the intermediary sets in maximum cardinality search optimal in some way?

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 ...
templatetypedef's user avatar
3 votes
1 answer
429 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 ...
Yixin Cao's user avatar
  • 2,559
14 votes
1 answer
607 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$ ...
Mathieu Mari's user avatar
4 votes
0 answers
217 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 ...
Matthias's user avatar
5 votes
0 answers
179 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 ...
Martin Hofmann's user avatar
1 vote
0 answers
86 views

Is it sufficient to only check on the vertices? Greedy algorithm

Suppose that I have a downwards closed Polyhedron and a vector $\omega$ and a greedy algorithm that goes as follows: Given an initial $x_0$, order the indices of $\omega$. Then for each $i$, solve $\...
user44975's user avatar
-1 votes
2 answers
3k views

Dynamic Programming vs Greedy Algorithm

In (Sniedovich 2006) "Dijkstra's algorithm revisited: the dynamic programming connexion", Sniedovich provides us another interpretation of Dijkstra's algorithm as a dynamic programming implementation. ...
Leo's user avatar
  • 91
2 votes
1 answer
603 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 ...
Johnatan Morian's user avatar
0 votes
2 answers
861 views

Packing $n$ objects into $m$ bins whose size is variable

Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put ...
mnmp's user avatar
  • 175
3 votes
1 answer
454 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, ...
Rahul Gopinath's user avatar
14 votes
1 answer
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 ...
Yuan Li's user avatar
  • 143
12 votes
0 answers
367 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 ...
Stasys's user avatar
  • 6,765
0 votes
0 answers
299 views

Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
fstab's user avatar
  • 119
15 votes
3 answers
3k 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 ...
user avatar
21 votes
2 answers
1k 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)$, ...
Yonatan's user avatar
  • 794
0 votes
0 answers
436 views

Worst case of heuristics for symmetric TSP

I have implemented the nearest neighbor heuristic for solving symmetric TSP problems. I was wondering if there is any relation between the solution found by the heuristic and the optimal solution? ...
user19553's user avatar
0 votes
1 answer
197 views

Planning jobs as partition problem

I think this should be a famous problem but I could not find its name. I have $n$ jobs with size $s_i$ that are offered at time $t_i$ and $k$ machines. How can I assign jobs to machines to minimize ...
Masood_mj's user avatar
  • 199
3 votes
2 answers
595 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 ...
David Chouinard's user avatar
1 vote
0 answers
927 views

Pure Greedy algorithms

I study pure greedy algorithms in different bases. I am interested in the following question: Is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that $$ \|f-G_m(f,D)\| > Cm^{-...
Studentmath's user avatar
0 votes
0 answers
89 views

Partitioning based on distribution

Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution. For two bins and uniform distribution, this problem is ...
Masood_mj's user avatar
  • 199
7 votes
1 answer
452 views

expected number of sets generated by greedy set cover ?

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 = \...
AJed's user avatar
  • 644
2 votes
4 answers
6k 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: ...
Jonny5's user avatar
  • 247
10 votes
3 answers
904 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 ...
ivotron's user avatar
  • 243
1 vote
0 answers
137 views

How to prove $k^{n-1}, k^{n-2}, \ldots, k^0$ will result with minimum number of coins? [closed]

I am not sure how to prove or disprove for $A_n = \{k^{n-1}, k^{n-2}, \ldots, k^0\}$ for some $k > 1$, the greedy method will yield solutions with minimum number of coins. I know that each number ...
Raptrex's user avatar
  • 111
39 votes
9 answers
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 ...
Shiva Kintali's user avatar