Questions about algorithms that make at each step the locally optimal choice.
1
vote
1answer
82 views
Dynamic programming VS Greedy Algroithms [on hold]
I have two True or False questions in my practice test that are related but I am unsure about:
...
1
vote
2answers
41 views
Correctness proof of greedy algorithm for 0-1 knapsack problem
We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an ...
1
vote
0answers
27 views
How to maximize the number of buyers in a shop?
There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items ...
2
votes
1answer
73 views
GSAT incompleteness example
The GSAT (Greedy Satisfiability) algorithm can be used to find a solution to a search problem encoded in CNF. I'm aware that since GSAT is greedy, it is incomplete (which means there would be cases ...
-1
votes
2answers
104 views
Proof of Correctness of Prim's algorithm [duplicate]
what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case?
Is it because of after any number of steps, $S$ might not be in a sub ...
-1
votes
1answer
108 views
Minimal Spanning tree and Prim's Algorithm
Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
-1
votes
2answers
79 views
Algorithm for sorting with constraints
I've got 30 elements which has to be grouped/sorted into 10 ordered 3-tuple.
There are several rules and constraints about grouping/sorting.
For example: Element $A$ must not be in the same tuple ...
1
vote
1answer
107 views
Finding an instance of an n-element set cover
Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter ...
1
vote
0answers
114 views
Single machine job scheduling (Greedy heuristic)
Here is a variation of a job-scheduling Problem.
Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge ...
1
vote
0answers
183 views
minimum cost path
Consider the following problem:
There are $n$ points in the plane.
Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way ...
-1
votes
1answer
176 views
How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n
How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ?
for example : for n=10
1
2
3
4
10
20
30
40
100
200
the sub-sequence of length ...
-1
votes
1answer
366 views
How to implement GREEDY-SET-COVER in a way that it runs in linear time [closed]
This is an exercise in the book Introduction to Algorithm, 3rd Edition.
The original question is:
Show how to implement GREEDY-SET-COVER in such a way that it runs in time ...
2
votes
0answers
115 views
Other greedy choices to solve activity selection problem
I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities.
But surely ...
2
votes
1answer
98 views
Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper
Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization ...
2
votes
2answers
1k views
Time complexity of a backtrack algorithm
I've developed the following backtrack algorithm, and I'm trying to find out it time complexity.
A set of $K$ integers defines a set of modular distances between all pairs of them. In this
algorithm, ...
0
votes
1answer
1k views
Proving greedy choice property of fractional knapsack
A typical way of proving the greedy choice property of the fractional knapsack problem is as follows:
From Slide 5 of this link:
Given: A set of items $I = \{I_1,I_2..I_n\}$ with weights ...
2
votes
2answers
1k views
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 ...
1
vote
0answers
171 views
Solving a variant of interval scheduling problem
I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have a ...
4
votes
1answer
199 views
Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have ...
2
votes
1answer
570 views
Fractional Knapsack in linear time
How to solve fractional knapsack in linear time? I found this on Google but don't really understand it.
Choose element $r$ at random from $R$ (set of profit/weight ratios)
Determine
$R_1 = \{ p_i ...
1
vote
3answers
379 views
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 ...
3
votes
2answers
407 views
Greedy Optimum Dominating Set For A Tree
I am trying to figure out a greedy algorithm that finds the optimum (minimum) dominating set for any tree in linear time.
So a greedy algorithm to find a dominating set for a general graph is not ...
3
votes
1answer
59 views
Show that approximation ratio for a convex hull algorithm is $\pi/2$
Facts: n points in the plane, each has one of k colors, all k colors are represented.
Problem: You wish to select k points, one of each color, such that the perimeter of the convex hull is as small ...
6
votes
0answers
97 views
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 ...
0
votes
1answer
605 views
Greedy algorithms tutorial
Could anyone point me to simple tutorial on greedy algorithm for Minimum Spanning tree - Kruskal's and Prims' Method
I am looking for a tutorial which
does not include all the mathematical ...
10
votes
1answer
3k views
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 ...
4
votes
1answer
174 views
Why do the swap step in Prim's algorithm for minimum spanning trees?
I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees.
Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
5
votes
1answer
196 views
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 ...
6
votes
2answers
264 views
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.
...
1
vote
2answers
278 views
“Flow layouts” inside a GUI — how do I come up with a good algorithm?
I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode):
...
1
vote
0answers
27 views
How to use greedy algorithm to solve this? [duplicate]
Possible Duplicate:
How to use greedy algorithm to solve this?
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 ...
17
votes
3answers
758 views
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 ...
