Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
299
questions
35
votes
2answers
32k views
How to prove greedy algorithm is correct
I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
2
votes
0answers
26 views
Maximize the minimum gap while scheduling within intervals?
Problem
There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals?
For ...
0
votes
2answers
56 views
Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?
There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:
There are n tasks, each task ...
0
votes
1answer
32 views
Mathematical expression for the quantity that we are maximising in the stock buying and selling problem
Problem Statement:
Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.
Design an algorithm to find the maximum profit. You may complete as many ...
0
votes
2answers
54 views
What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]
I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, ...
-1
votes
1answer
34 views
Prove following statement about Kruskal Algorithm
Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
0
votes
0answers
49 views
Find the maximum number of valid cartesian coordinates
Given a list X containing m number of x coordinates and a list Y containing m number of y coordinates. The coordinate (x, y) is valid if and only if the difference between x and y is less than or ...
2
votes
1answer
306 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
1
vote
2answers
226 views
FInding the combination with the least number of elements from and array of integers, given an integer sum
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
0answers
36 views
Choosing a method for algorithmic problems - is it an art or science?
I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
0
votes
1answer
80 views
Binary string satisfying several constraints
I'm trying to solve this problem, but without success.
Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...
0
votes
0answers
18 views
Minimizing the length a Boolean Algebra Expression in disjunctive normal form
I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
1
vote
0answers
44 views
Algorithm for summation with lowest maximum temporary sum
I've got this problem on my last exam, which I struggle to deal with.
Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
4
votes
1answer
270 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 ...
8
votes
1answer
368 views
The heaviest induced subgraph problem
I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
3
votes
1answer
3k views
Maximum cut using a 1/2 approximation greedy algorithm
I have the following greedy algorithm for max cut problem:
Initialization: $A \leftarrow \{v_1\}$ , $B \leftarrow \{v_2\}$
For $v \in V − \{v_1, v_2\}$ do:
if $d(v,A) \geq d(v,B)$ then $B \...
2
votes
1answer
70 views
Using a greedy algorithm to find a cut S which at least half of the edges cut
Let $G$ be an undirected graph.
Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.
I tried to think about something like choosing the vertex with the highest degree, ...
4
votes
2answers
219 views
Difficulty in understanding the proof of the lemma : “Matroids exhibit the optimal-substructure property”
I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma ...
0
votes
1answer
154 views
Greedy sequential/parallel task scheduling
We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and ...
0
votes
1answer
21 views
An independent d-division
I would love to have a direction for the following exercise (the material for this exercise is greedy algorithms):
Let $G = (V,E)$ an undirected graph whose vertices $V = \{v_1,\dots,v_n\}$ appear in ...
0
votes
1answer
35 views
Negative cycle detection using Bellman-Ford and its correctness
I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.
I have 2 doubts about the correctness of the algorithm:
Why are we ...
0
votes
0answers
29 views
Scheduling algorithm for overlapping jobs - single resource?
I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are ...
0
votes
1answer
52 views
Three City Scheduling
I came across the following interview question
There are 2N people a company is planning to interview. The cost of
flying the i-th person to city A is costs[i][0], and the cost of
flying the i-...
1
vote
0answers
27 views
Remove vertices to get k-connected components
In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?
1
vote
1answer
49 views
Problem related to set partitioning
Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$
Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one ...
0
votes
0answers
19 views
Set Cover: Understanding the algorithm with an example
I am trying to follow the following link:
Solution for an example
They have provided solution for an example using the greedy algorithm. I have got following questions:
(1)Why start with Z, cost is 7, ...
0
votes
0answers
31 views
Does this problem have a formal name?
I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. ...
0
votes
1answer
124 views
Minimum steps to sort array [closed]
Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values ...
4
votes
2answers
2k 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 ...
2
votes
1answer
51 views
Proof of a greedy algorithm used for a variation of bin-packing problem
We are given an array of weights $W$ (all weights are positive integers), and we need to put the
weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The ...
2
votes
3answers
664 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 ...
1
vote
1answer
13 views
How proof of Hoffman algorithm greedy property starts with optimal tree T?
In this paper Claim 1 states that x and y are smallest probability and there is optimal code tree in which this two characters are siblings at the maximum depth. In proof to that claim, author starts ...
0
votes
2answers
478 views
Maximize the sum of chosen numbers
I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem.
Suppose there is a game with 2 players, A and B and a ...
1
vote
0answers
41 views
Greedy algorithm to divide objects into the lowest number of groups of a maximum size
I have n objects of independent size s, and need to group them so that the sum of the sizes of each group is smaller than a given maximum size, and the number of groups is the smallest possible.
I ...
2
votes
1answer
147 views
N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm
So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its ...
1
vote
1answer
55 views
Proof for an algorithm to minimize $\max(a, b, c) - \min(a, b, c), a \in A, b \in B, c\in C$, A, B, C are arrays in ascending order
Problem Statement
I came across this problem here. For given arrays $A$, $B$ and $C$ arranged in ascending order, we need to minimize the objective function $f(a, b, c) = \max(a, b, c) - \min(a, b, c)...
3
votes
2answers
422 views
Merging balls interview problem
Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.
You are given $n$ balls on the table and all the balls are rolling towards the ...
1
vote
0answers
47 views
Looking for an algorithm or similar mathematical problem for trading ownerships in shared property
Suppose there is $N$ property. Each property is owned by multiple person. (they have shared ownership) For example: $Person_1$ owns 22% of $Property_1$, $Person_2$ owns 35% of $Property_1$ and $...
2
votes
1answer
303 views
Gas Station Problem - Dijkstra's Algorithm variation
I am trying to find an algorithm which finds the least expensive route from one town to another.
This is the general setup.
There are a series of one-way roads from some towns to other towns. Not ...
2
votes
3answers
3k views
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.
This question is a simplification of ...
1
vote
2answers
74 views
Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines
I'm trying to prove a greedy algorithm works for a specific problem:
You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run ...
1
vote
1answer
53 views
center selection problem: Simple greedy algorithm
I am trying to understand the following text which defines a greedy algorithm for center selection problem:
It would put the first center at the best possible location for a
single center, then ...
0
votes
1answer
44 views
When does this algorithm fail?
The problem
Given $n$ stacks of $k$ integers each. What is the maximum sum that can be achieved by removing exactly $p$ integers?
The following example illustrates the problem.
$n$ = 3, $k$ = 4, $...
-1
votes
1answer
31 views
Find bipartial subgraph such that sum of edge lengths is maximum
Let there be graph $G = (V, E)$. $G$ has neither loops nor parallel arcs.
$V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$
For simplicity's sake, let's consider $G$ is ...
0
votes
1answer
15 views
Allocating tasks among two people equitably
Given that we have 2 people, and 2n tasks, find the minimum time to complete the tasks. Both persons should solve exactly n tasks each and any task j has to be solved before task j+1. Required time ...
0
votes
0answers
36 views
How to prove optimal substructure for Lecture Hall assignment problem?
In CLRS, an approach has been given to prove the optimal substructure and the correctness of the greedy algorithm for the activity selection problem. In the Lecture Hall assignment problem, we sort ...
1
vote
0answers
30 views
What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?
Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem).
A trivial ...
-1
votes
1answer
91 views
Variations of Activity Scheduling Algorithm
I've been following Greedy algorithms in the textbook Jeff Erickson. Here is the following Question I was stuck in proving Proof of Correctness for the following variant of the standard Activity ...
0
votes
1answer
215 views
Proving a Greedy Algorithm is Incorrect by Providing Counter Example and Coming up with another correct algorithm
I want to come up with a counter example that proves the following greedy algorithm doesn't work and give an alternative correct algorithm. The problem is I have an array of numbers and I want to ...
1
vote
2answers
94 views
Proof by contradiction for greedy algorithms
I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never ...
