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

learn more… | top users | synonyms

0
votes
0answers
11 views

What is the approximation ratio of the following grid-cover algorithm?

Given is a $N\times M$ grid. A greedy algorithm wishes to cover all coordinates in the greedy by $k$-sized rectangles. At each iteration, it chooses a rectangle of area $\le k$ which covers as many ...
0
votes
1answer
17 views

Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some ...
0
votes
1answer
40 views

People crossing a bridge (a proof for a greedy algorithm)

The problem Some people are crossing a bridge. Each one takes a different time to pass. Assume the people are sorted by their passing time increasingly. These are the conditions of crossing the ...
0
votes
1answer
29 views

Interval scheduling scheduling problem with minimal workers

I am writing a greedy algorithm for a variation of the interval scheduling problem that I haven't seen before. I have a set of jobs, each with start and finish time. All jobs in set must be assigned ...
1
vote
1answer
31 views

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, ...
0
votes
1answer
26 views

Huffman code optimal substructure property

I am learning about Greedy Algorithms and we did an example on Huffman codes. To prove the correctness of our algorithm, we had to have the greedy choice property and the optimal substructure ...
2
votes
1answer
50 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
1
vote
1answer
39 views

can sampling remove the limitations in greedy algorithm

knowing this is a vague question, but i just want to know that, given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or ...
0
votes
1answer
48 views

Sorted-greedy for Load Balancing Problem

In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t_j$. Total processing time on the machine $i$ is $T_i =\sum_{j\in A(i)}{t_j}$, where $A(i)$ is the set of ...
1
vote
2answers
302 views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
1
vote
1answer
109 views

Find a quarrel-free seating order with a greedy algorithm [duplicate]

I'm revising for an Algorithms exam and looking at a sample question it says : A group of n teenagers $t_1, \dots, t_n$ are to sit in a single row of n chairs watching a particulary boring comedy ...
1
vote
1answer
20 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
2
votes
1answer
69 views

Greedy proof: Correctness versus optimality

I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same ...
4
votes
2answers
119 views

Do all greedy algorithm produce just the first solution, no matter how bad it is?

In all the exampls of the greedy algorithms I've seen so far, such as activity selection problem and unit-sized set coverage problem, the algorithm is usually very simple and intuitive and returns the ...
1
vote
2answers
97 views

Find the coins required which sum to S

Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once). I was recently studying ...
3
votes
1answer
99 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
-1
votes
1answer
23 views

How do you come up with greedy algorithm for deadline scheduling when comparing x_subscript(i) and y_subscript(k)?

So there are two boxing teams, my team A and the opposing team B, each with m boxers. Based on the player's ranking of skill, x_subscript(i) being the ranking for ith boxer for team A and ...
0
votes
2answers
195 views

minimum spanning tree and minimum heavyweight spanning tree

a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible. Formally, input : given connected undirected weighted graph, $G$. output : a spanning tree ...
0
votes
0answers
91 views

stuck on proving the optimality of a greedy algorithm [closed]

I'm Ph.D. student doing research in wireless networks. My past projects are more oriented to systems than theory. For my current project, I devised a greedy algorithm for an optimization problem. ...
-1
votes
1answer
59 views

Minimising two maximum edges in s-t path

I've been trying to solve the following problem: Problem is the following: Given a graph and a pair of nodes $s$, $t$ you have to find the path from $s$ to $t$ which minimises the sum of its two ...
-2
votes
1answer
39 views

How to figure out the minimal number of colors needed to color specific given graphs?

I found this question on the net and I'm wondering what is the process for answering such questions? I assume there is some formula that works for all graphs? 1.a. Consider the undirected graph with ...
3
votes
1answer
359 views

Fast algorithm for matrix chain multiplication in special case

An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots ...
0
votes
2answers
53 views

Greedily Schedule Events based on value/hours

Suppose we are given a list of $n$ events $E = \{E_1, E_2, \ldots, E_n\}$ where each $E_i$ is represented by $(s_i, h_i, v_i)$ or $(start, hours, value)$. So if you attend an entire event that lasts ...
3
votes
2answers
76 views

Minimizing Cost by minimizing delay

There is a complete binary tree with its leaves as components of some system The values from one node to another gives propagation time for a signal to propagate from one junction to another For ...
1
vote
0answers
28 views

Conjecture about a matrix column swapping challenge problem

So here is the challenge problem statement: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1512 Basically, given a 0/1 matrix, you ...
1
vote
1answer
297 views

Dynamic programming VS Greedy Algroithms [closed]

I have two True or False questions in my practice test that are related but I am unsure about: ...
1
vote
2answers
470 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
32 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
137 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
324 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
290 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
129 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
171 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 ...
2
votes
0answers
184 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
351 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
469 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 ...
0
votes
1answer
1k 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
193 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
117 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
3k 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
3k 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 ...
7
votes
2answers
4k 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 ...
2
votes
1answer
343 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
259 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
2k 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 ...
5
votes
4answers
2k 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
705 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
74 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 ...
7
votes
0answers
120 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
893 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 ...