The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
0
votes
2answers
194 views

Minimizing the overall cost over groups

I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this: ...
0
votes
1answer
466 views

Please check my Huffman tree [closed]

My professor gave an example of Huffman tree. Given inputs a 80 b 10 c 20 d 50 e 100 f 35 g 60 … then the tree will be: But when i tried to solve it at home, I ...
4
votes
1answer
228 views

An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

Suppose there is an unlimited number of pipes, each has length $x$ meters. There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given. For example ...
4
votes
2answers
224 views

Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
-1
votes
1answer
63 views

Optimal way to join pieces when the cost of joining two pieces is $|x-y|$

There are $N$ pieces each having size $A_i$. The cost of joining a piece of size $x$ and a piece of size $y$ is $|x-y|$. What is the most optimal way to join all the pieces? Can it be solved using the ...
2
votes
1answer
2k views

A greedy approximation algorithm for max k-cut

The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$ so that the total cost of edges running ...
1
vote
1answer
87 views

Information about ε-greedy algorithms

I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms ...
7
votes
1answer
2k 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 ...
2
votes
0answers
122 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 $H$ is the current graph, until there are no more cycles left. (...
0
votes
0answers
46 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$, ...
3
votes
4answers
2k views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
2
votes
1answer
549 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
95 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
2answers
871 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
489 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 ...
2
votes
2answers
604 views

Coin Change Problem(Greedy Algorithm)

In Coin Change Problem, if the ratio of Coin Value ($\frac{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 ...
3
votes
2answers
636 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 $(\ln n+...
5
votes
1answer
424 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 ...
4
votes
1answer
408 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
184 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 ...
3
votes
1answer
2k 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 ...
3
votes
1answer
4k 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
921 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
2k 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) ...
3
votes
1answer
151 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 ...
6
votes
5answers
1k 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
412 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 ...
4
votes
1answer
93 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 ...
3
votes
1answer
2k 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 some ...
3
votes
0answers
210 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 ...
2
votes
1answer
2k 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 ...
1
vote
1answer
2k 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
2k 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 ...
6
votes
2answers
3k 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
928 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 property....
2
votes
1answer
286 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
248 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 ...
0
votes
1answer
2k 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 ...
5
votes
2answers
5k 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
542 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 ...
2
votes
1answer
87 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 ...
4
votes
1answer
1k 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
500 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
306 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
229 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
161 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 y_subscript(...
2
votes
2answers
683 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 $T$...
-1
votes
1answer
104 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
919 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
2k 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 \...