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

learn more… | top users | synonyms

3
votes
1answer
67 views

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 ...
1
vote
0answers
20 views

Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $Η$ is the current graph, until there are no more cycles left.What ...
0
votes
0answers
23 views

Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...
1
vote
2answers
143 views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
1
vote
1answer
72 views

Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
1
vote
0answers
39 views

find max k sequence - is it greedy?

The original problem statement is: Given a sequence of numbers $A[1..n]$, find $k < n$ consecutive numbers such that the sum of these $k$ numbers is maximized where $k$ is a positive ...
5
votes
3answers
489 views

Counterexample to this modified Dijkstra's

In class, we were given the following problem: We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v) which is a real number in the range 0 ≤ r(u, ...
1
vote
5answers
163 views

Correctness of the greedy algorithm

I am trying to solve the following problem: Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of ...
0
votes
1answer
56 views

Coin Change Problem(Greedy Algorithm)

In Coin Change Problem, If the ratio of Coin Value(Coin(i+1)/coin(i)) is always increasing then we can use Greedy Algorithm? Example- 1,3,4 are denominations of coin. If I want to pay Rs.6 then the ...
2
votes
1answer
60 views

Is greedy algorithm the best algorithm for set cover problem?

Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem. I am a bit confused by this theorem. As we know, greedy algorithm is ...
4
votes
1answer
69 views

Variations of Greedy Algorithm

What is the definition of an "orthogonal greedy algorithm"? What is the definition of a "relaxed greedy algorithms"? Can you give an example to illustrate how these notions differ from ordinary ...
2
votes
1answer
143 views

2 approximation algorithm for the single machine scheduling problem

We are given one machine and $n$ jobs that we want to process. For the $n$ jobs we have the following data: $r_{1}, ... , r_{n}$ are the release times $p_{1}, ... , p_{n}$ are the processing times ...
1
vote
0answers
36 views

convex hull for unsorted vertices solved by graham scan algorithm

can graham scan algorithm work with convex hull vertices when vertices are not sorted? I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by ...
2
votes
1answer
94 views

greedy algorithm for Maximum directed cut [closed]

Maximum directed cut: Given a directed graph $G = (V, E)$ with nonnegative edge costs, find a subset $S \subseteq V$ to maximize the total cost of edges out of $S$: $\mathrm{cost}( \{ (u \to v) \mid ...
2
votes
1answer
195 views

Matrix Chain Multiplication Greedy Approach

In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic ...
3
votes
1answer
69 views

Easiest improvement on first-fit for bin packing algorithm

See the interactive example here. First-fit on the left, optimal on the right. I know that in general, optimal bin-packing is NP-hard, so I'm not looking for a perfect solution. I'm looking for the ...
2
votes
2answers
175 views

Delivery Algorithm - Find shortest paths

Given - A center(lat=x,lng=y) 'C' from which a delivery boy makes a round trip. A delivery boy has a bag which may contain at the most 10 boxes to deliver. A set of points Di (lat=xi,lng=yi) ...
2
votes
1answer
58 views

Greedy algorithm proof

There are 2n product and their prices: P={p_1, p_2, ..., p_2n}. When we buy the products in pairs we get the product with lower ...
5
votes
5answers
255 views

Please explain a greedy algorithm in a naive manner [closed]

I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms. From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local ...
4
votes
1answer
142 views

Greedy algorithm correctness proof for “Elegant Permuted Sum” (UVa 11158)

Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized. I found many ...
3
votes
1answer
55 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
2
votes
1answer
126 views

Relation between the “Point-Cover-Interval” problem and the “Interval Scheduling” problem

Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains ...
3
votes
0answers
71 views

Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
1
vote
1answer
193 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
223 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
242 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
112 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, ...
1
vote
1answer
100 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
74 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
89 views

Can sampling remove the limitations in greedy algorithm?

Given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or some structured manner reduce or remove the limitations of ...
1
vote
1answer
187 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
969 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
145 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
29 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
321 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 ...
5
votes
2answers
148 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
134 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
134 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
49 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 ...
2
votes
2answers
248 views

minimum spanning tree and minimum heavyweight spanning tree [duplicate]

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
108 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
69 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
87 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
506 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
77 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
82 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
29 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
670 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
762 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
33 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 ...