23
Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing.
Random testing
As a first step, I recommend you use random testing to test your algorithm. It's amazing how effective this is: in my ...
18
It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching).
Nick Harvey did his Ph.D thesis ...
14
I will use the following simple sorting algorithm as an example:
repeat:
if there are adjacent items in the wrong order:
pick one such pair and swap
else
break
To prove the correctness I use two steps.
First I show that the algorithm always terminates.
Then I show that the solution where it terminates is the one I want.
For the first point,...
13
A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts.
The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of ...
11
We first observe the following: There is an optimal cover $C$, and no leaf is in $C$. This is true since in any optimal cover $X$ you can replace all leaves in $X$ with their parents, and you get a vertex cover which is not larger than $X$.
Now take any optimal cover $C$ that does not contain leaves. Since no leave is selected, all parents of the leaves ...
9
Let's start with the following observation:
Let $max$ denote the maximum of the sequence $a_1,...,a_n$, and let $min$ denote its minimum. If $a_1=max$, then choosing $b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$ is optimal.
Why is this the case? Well, since the sequence starts with the maximum, either we choose $b_1$ large, and suffer a large deviation ...
8
It would be nice if you stated the problem. I assume that you have $n$ items $x_i$, each having profit $p_i$ and weight $w_i$. You want to maximize your profit under the constraint that the total weight is at most $W$. For each item $x_i$, you are allowed to put any fraction $\theta \in [0,1]$ of it, which will give you profit $\theta p_i$ and weight $\theta ...
8
Your algorithm makes the wrong choice between the following two paths:
5 channels with a reliability of 50% (combined reliability 3.125%), weight $5 \cdot {1 \over 0.50} = 10$.
A single channel with a reliability of 8%, weight ${1 \over 0.08} = 12.5$.
7
The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver.
...
7
In simple words, an algorithm is normally considered "greedy" if
it builds solutions step by step without backtracking
in each step it picks what's best in the current state.
To learn more about it, check this pdf out.
The animated gif above illustrates a greedy algorithm for finding the path that adds up to the biggest number.
It does so by choosing ...
6
Greedy algorithm can't help in that case. And it couldn't be compared with both fractional or 0-1 knapsack problems. The first could be resolved by greedy algorithm in O(n) and the second is NP.
The problem you have could be brute-forced in O(2^n). But you could optimize it using dynamic programming.
1) Sort intervals by start time.
2) Initialize int[] ...
6
The running time of your algorithm is at most $N (N-1) (N-2) \cdots (N-K+1)$, i.e., $N!/(N-K)!$. This is $O(N^K)$, i.e., exponential in $K$.
Justification: There are $N$ possible choices for what you put into the first blank, and in the worst case you might have to explore each. There are $N-1$ choices for the second blank, and so on. You can draw a tree ...
6
Here is a simple definition for greedy algorithm.
There are many greedy algorithms for different problems and in order to understand them you must also know well the subject of the problem. This question on stackoverflow gives some examples of greedy algorithms usage.
EDIT : After you made your question more clear I will try to sketch the algorithms by ...
6
The connection is that if a you can represent the structure underlying your optimisation problem as matroid, you can use the canonical greedy algorithm to optimise the sum of any positive weight function. If your optimisation goal fits this paradigm, you can solve your problem with the greedy approach.
Example
Consider the minimum spanning tree problem ...
6
Yes, this is the idea of greedy algorithms, also known as myopic algorithms. There is still a lot of freedom in deciding what the myopic choice is based on. Allan Borodin has developed a theory of priority algorithms formalizing the notion of greedy algorithm. Such a theory can be used to analyze what greedy algorithms cannot do.
Sometimes greedy algorithms ...
6
Overview of the problem
If you takes teenagers as vertices of a graph, and have an edge
whenever the two teenagers are compatible. This gives you an
undirected graph, and what you need is a Hamiltonian path in this
graph (a path that contains every node exactly once). Maybe searching
the web on this abstract version of the problem will yield more
...
6
It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as myopic algorithms) being only one of them. That said, I have a positive answer and a negative answer for you.
Positive answer. Consider the problem of maximizing a ...
6
You don't state why you think that your algorithm is correct. In fact, it is incorrect. Here is an example. Consider the problem of computing the product of matrices of dimensions $2\times 1$, $1\times 2$, $2 \times 5$. Your algorithm first multiplies the first two at a cost of $4$, and then multiplies the remaining matrices at a cost of $20$, to a total of $...
6
The starting point is the trivial random algorithm that chooses $S$ completely at random. Each directed edge is cut with probability $1/4$ (why?), and so in expectation, this random algorithm gives a $1/4$ approximation.
We can derandomize this algorithm using the method of conditional expectations. Arrange the points in order: $1,\ldots,n$. At step $i$, we ...
6
Reduction from 3-SAT:
a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word.
e.g.
3 SAT: (a,b,-c) && (-b,c) =>
pairs: (a,-a), (b,-b), (c,-c).
words: (a,b,-c), (-b,c)
Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding ...
6
There is no such thing as the correct generalization of the greedy selection technique, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with a view toward understanding its limitations. This study has been initiated by Borodin, Nielsen and Rackoff, (Incremental) priority algorithms, and continued ...
5
So this question has been bothering me: why a cactus, if there's already a linear-time algorithm for a more general class?
The primal problem is known as the fractional matching problem, and, unsurprisingly, it has been studied as well. Balinski (whose result was made known to me via Schrijver's book Combinatorial Optimization) characterized the extreme ...
5
One could implement this in O(nlogn)
Steps:
Sort the intervals based on end time
define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn
define d[i] = max(w(i) + d[p(i)], d[i-1]).
initialize d[0] = 0
The result will be in d[n] n- the number of intervals.
...
5
There is a simple dynamic programming algorithm. Root the tree at some arbitrary vertex. For each subtree, compute the optimal dominating set (a) with the root, (b) without the root.
5
The idea of the backtracking algorithm is simple, though somewhat cumbersome to express. Perhaps it's easiest to explain it working through the example in the question. We start by putting $T_1$ on chair 1. We then put $T_2$ on chair 2. Then we put $T_3$ on chair 3, and we discover a conflict. So we backtrack, replacing $T_3$ with the next available student. ...
5
Your understanding is completely wrong: what you describe is known as hill climbing or gradient descent in the continuous case, and local search in the discrete case.
The best way to understand what greedy algorithms are is by an example. Consider the following optimization problem:
Given a set $S$ of positive integers and a number $n$, choose a subset ...
5
Greedy algorithms can be used whenever you can think of the solution to the problem being reached in steps. The strategy is then just to choose the next step that looks best in some (usually simple, "local") sense, without ever undoing a step and trying an alternative path.
The classical example is finding a minimal cost spanning tree of a graph. One ...
5
If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.
But there is an 8 blocks solution (on the right).
The problem with a greedy approach is that "consuming" a block can destroy two other possible blocks, and have a negative impact.
Repeating the search in different directions will not ...
5
Suppose that numbers are $x_1, \ldots x_{2n}$, and let us rename them as $a_1, \ldots a_n, b_1, \ldots, b_n$, where $a_i \geq b_j$ for any $i, j$, $a_1 \geq a_2 \geq \ldots \geq a_n$, and $b_1 \leq b_2 \leq \ldots \leq b_n$. In this notation, the suggested optimum solution is $(a_1, b_1), \ldots (a_n, b_n)$.
Given some arbitrary pairing, let us show we can ...
4
Here is some Python code that should implement Greedy Set Cover in linear time:
(Warning, it empties the input sets during the processing!)
from collections import defaultdict
F = [set([1,2,3]),
set([3,4,5,6]),
set([2])]
# First prepare a list of all sets where each element appears
D = defaultdict(list)
for y,S in enumerate(F):
for a in S:
...
Only top voted, non community-wiki answers of a minimum length are eligible
