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
0answers
357 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 ...
5
votes
0answers
72 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
0answers
174 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
0answers
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 ...
2
votes
0answers
70 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
0answers
70 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
vote
0answers
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 $\...
1
vote
0answers
858 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
0answers
296 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): ...
0
votes
0answers
418 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
0answers
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 ...
-2
votes
1answer
56 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 ...