Questions tagged [greedy-algorithms]
An algorithm which at every point makes the locally optimal choice.
12
questions with no upvoted or accepted answers
12
votes
0
answers
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
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 ...
- 593
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
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 ... ...
- 299
1
vote
0
answers
71
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 ...
- 1,901
1
vote
0
answers
84
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
vote
0
answers
899
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
298
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
0
votes
0
answers
420
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
0
answers
88
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 ...
- 189
-2
votes
1
answer
58
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 ...
