Questions tagged [greedy-algorithms]

Questions about algorithms that make at each step the locally optimal choice.

455 questions
50
votes
6 answers

How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there common patterns or techniques? I'm hoping this will…
D.W.
  • 170,893
  • 23
  • 241
  • 528
30
votes
1 answer

When can a greedy algorithm solve the coin change problem?

Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v. E.g. for the coinset 1,5,10,20 this gives 2 coins for the sum 6 and 6 coins for the sum 19. My…
The Unfun Cat
  • 1,833
  • 2
  • 20
  • 29
23
votes
1 answer

How fundamental are matroids and greedoids in algorithm design?

Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy algorithms to find optimal solutions. The…
Nicholas Mancuso
  • 3,937
  • 1
  • 26
  • 40
21
votes
4 answers

How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-decreasing sequence. Define the deviation of such a…
Aden Dong
  • 1,151
  • 2
  • 11
  • 24
15
votes
2 answers

Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover). For each internal node: if any of its children is not…
e_noether
  • 1,339
  • 2
  • 13
  • 19
10
votes
2 answers

Knapsack Greedy Approximation: Worst Case

I am currently studying approximation algorithms and I have run into an issue with a study problem. The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, where it sorts by the value/weight ratio, and…
Chris Chambers
  • 201
  • 2
  • 3
9
votes
1 answer

Fixed-length decision-tree-like feature selection to minimize average search performance

I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear search is $t\cdot |S|$. I can break a query down…
Andrew Dalke
  • 221
  • 1
  • 4
9
votes
1 answer

Optimality of DSATUR on interval graphs

The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm , considering vertices in reverse lexicographic order of (number of different colors among neighbours, total number of neighbours)…
Nathaniel
  • 19,072
  • 2
  • 32
  • 61
8
votes
1 answer

The heaviest induced subgraph problem

I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ of $G$ that maximizes the sum: $ \sum_{e \in E'}…
Łukasz Kuszner
  • 141
  • 5
8
votes
0 answers

Correctness of a greedy Algorithm on Knockout Tournaments

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a random way, so that when player $i$ faces player…
Guanaco96
  • 111
  • 4
8
votes
4 answers

Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum. Now I'm not sure if a greedy algorithm will do the trick. That is, sort by cost and always take the next job that doesn't…
user1531186
  • 89
  • 1
  • 1
  • 2
7
votes
1 answer

Greedy strategy for computing the minimum number of rays that hit all balloons

The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm" . The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the plane, each specified by its radius and the $(x,…
pinoyboy
  • 133
  • 1
  • 5
7
votes
1 answer

Greedy choice and matroids (greedoids)

As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I have roughly understood what matroids are. But how…
Imposter
  • 167
  • 7
7
votes
2 answers

Balanced weighting of edges in cactus graph

Given a cactus , we want to weight its edges in such a way that For each vertex, the sum of the weights of edges incident to the vertex is no more than 1. The sum of all edge weights is maximized. Clearly the answer is no more than $\frac{n}{2}$ for…
dysonsfrog
  • 227
  • 1
  • 4
6
votes
1 answer

Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Definitions: An up down language is a language whose alphabet is a set of pairs , but not characters, of two characters, where the one character in the pair is the opposite of the other character in the pair. Each word in the language is…
Farewell Stack Exchange
  • 381
  • 2
  • 17
1
2 3
…
30 31