Questions tagged [greedy-algorithms]
An algorithm which at every point makes the locally optimal choice.
31
questions
1
vote
1
answer
222
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:
...
4
votes
2
answers
245
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. ...
- 89
2
votes
0
answers
98
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 ... ...
- 369
-2
votes
1
answer
70
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 ...
5
votes
0
answers
92
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, ...
- 9,595
3
votes
1
answer
300
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. ...
1
vote
0
answers
85
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 ...
- 2,121
3
votes
1
answer
390
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,560
14
votes
1
answer
601
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$ ...
- 475
4
votes
0
answers
214
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 ...
- 61
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 ...
- 643
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 $\...
- 19
-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. ...
- 91
2
votes
1
answer
597
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 ...
0
votes
2
answers
831
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 ...
- 175
3
votes
1
answer
447
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, ...
- 175
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 ...
- 143
12
votes
0
answers
364
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,685
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):
...
- 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 ...
user3373748
21
votes
2
answers
988
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
0
votes
0
answers
431
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?
...
0
votes
1
answer
196
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 ...
- 199
3
votes
2
answers
591
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 ...
- 133
1
vote
0
answers
925
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^{-...
- 11
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 ...
- 199
7
votes
1
answer
448
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 = \...
- 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:
...
- 247
10
votes
3
answers
893
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
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 ...
- 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 ...
- 10.6k