# Questions tagged [greedy-algorithms]

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

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
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

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^{-...
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 ...