Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
2
votes
4answers
59 views
A greedy algorithm for the bottle filling problem
(There’s no need to write the algorithm, I just need help with the greedy choice).
Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We ...
0
votes
1answer
34 views
Given n drinks, find optimum way to spend money if for each drink the price and the expiration date is given
Let's say we are given $n$ types of drinks, integer $m$ representing the budget we have and integer $d$ representing the cost of delivery when we order some drinks. For each of the $n$ drinks we are ...
0
votes
1answer
22 views
How this proof of fractional knapsack works?
I don't understand a step in my book proving the fractional knapsack problem:
Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by ...
1
vote
2answers
42 views
set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
1answer
25 views
Greedy Algorithm Proof Min Swaps
Problem to get the min. no. of swaps required for arranging pairs togethe.
There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with ...
1
vote
0answers
23 views
directed edges in an undirected graph [duplicate]
Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even.
For example, consider a graph ...
1
vote
1answer
76 views
What is the optimal way to solve the following optimization problem
You are given a function $F$, which can take one or more positive integer operands.
Let $L=\{a_1,a_2\ldots a_n\}$.
We need to compute the function $F(L)$ using the least number of transformations/...
0
votes
2answers
32 views
MST Proof (Kleinburg & Tordos)
Consider the Minimum Spanning Tree Problem on an undirected graph
G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all
be different. If the costs are not all distinct, there can in ...
1
vote
1answer
41 views
Greedy algorithm to find Minimum Dominating Set in a tree
Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
1
vote
1answer
61 views
Solving “coin exchange” for coins of power values by greedy algorithm
When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$?
For ...
0
votes
1answer
31 views
interval scheduling algorithm
can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this ...
1
vote
1answer
44 views
Variant of interval scheduling with varying task durations
I am probably just missing the correct term for my problem to find the solution but here it goes:
I have a set of tasks with a given duration and an interval for each task in which it has to be ...
-1
votes
0answers
59 views
How we can minimize number of boxes for packing objects
Imagine we have n objects with different weights.
We know the order in which objects come into the packing machine. Packing machine have two boxes, their capacity are equal and constant. When an ...
0
votes
0answers
34 views
Designing a greedy algorithm concerning “Machine Allocation Problem”
There are $m$ machines and $n$ tasks. Each task $i$ contains a time interval $[a_i,b_i]$ and a specified machine $c_i$ denoting that we should choose one day $a_i \le t_i \le b_i$ ($t_i$ must be an ...
1
vote
1answer
57 views
Algorithm to organize a tournament where the team componentes change each round
So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
2
votes
0answers
32 views
Weighted Sorting Algorithm
Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation.
Is there any ...
1
vote
1answer
123 views
Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?
Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
1
vote
1answer
62 views
Correctness proof for greedy algorithm based on ratio
I've an issue stated as follows:
We have 10000 jobs to do, each with some length $l_i$ and weight
(importance) $w_i$. Our goal is to arrange the schedule of doing these
jobs (in other words, ...
1
vote
2answers
62 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
1answer
60 views
Minimum Number of Integers From a List that Add up to N (Dynamic Programming)
A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:
Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where ...
3
votes
2answers
88 views
Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?
I came across this problem in Tim Roughgarden's course on Coursera:
In this problem you are given as input a graph $T=(V,E)$ that is a
tree (that is, $T$ is undirected, connected, and acyclic). A ...
1
vote
1answer
248 views
Proof of a greedy algorithm concerning “Buy and Resell Problem”
"Buy and Resell Problem" can be described in the following way:
There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from ...
2
votes
2answers
384 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 ...
2
votes
0answers
52 views
Maximum number of non-overlapping rectangles where each contains a minimum number of points
Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
2
votes
1answer
55 views
Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks
Lets just say I have two lists of the running time of tasks A and B. Formally, I would have:
A = {a_1, a_2, a_3 ... a_n}
B = {b_1, b_2, b_3 ... b_n}
I can only ...
1
vote
1answer
29 views
Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?
I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, ...
1
vote
1answer
46 views
Candy Problem for k size window
I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) ...
2
votes
1answer
51 views
Mimimum spanning tree with a constraint on number of certain types of edges
I have the the following problem.
Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
1
vote
1answer
37 views
what is the significance of the word “Sub-problems” in Greedy Method?
With respect to Dynamic Programming we make a statement that :
Greedy algorithm have a local choice of the sub-problems whereas
Dynamic programming would solve the all sub-problems and then ...
0
votes
1answer
148 views
Can Tug of war problem be solved by DP or greedy approach?
For problem explanation: https://www.geeksforgeeks.org/tug-of-war/
I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ...
2
votes
1answer
45 views
How to restore diagonal-symmetric matrix that has been shuffled?
I have a square matrix M, which originally looked like this:
133 199 101 121
142 133 199 101
156 142 133 199
108 156 142 133
(so symmetric around the diagonal). ...
1
vote
1answer
85 views
Why this greedy algorithm does not return the optimal solution to this NP-hard problem?
Problem:
In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective ...
2
votes
2answers
62 views
Shortest travelling cost if we have bunch of points in 2D plane
I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
0
votes
1answer
37 views
Minimum square side length to enclose n circles of radius r
I thought of a problem but have no idea how to solve it. The problem is as follows:
Given 2 numbers, n and r, find the side length (S) of the smallest square that encloses n circles each of radius r ...
0
votes
1answer
143 views
proof of correctness for greedy knapsack algorithm
I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement ...
0
votes
1answer
144 views
Does an algorithm exist for scheduling jobs on two processors?
I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found ...
1
vote
1answer
35 views
Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit
I have such a task at university:
we have n tasks, i-th of them can be done between moment b(i) and e(i). If we decide to perform a task in moment x, we finish performing it in moment x+1. We can ...
0
votes
0answers
64 views
How to approach solving this variation of the Job Scheduling Problem?
Question: Given N processes with Arrival times and Processing times, calculate and print minimum number of CPUs required if maximum allowed Turnaround time for each process is 10 units.
Turnaround ...
0
votes
1answer
21 views
Interval Scheduling Confusion
I am reading some notes about interval scheduling. I gives the following diagram:
and states that:
r2 is compatible with r3, while r2 and r1 are conflicting. Similarly, the set {r1, r3, r4} is ...
0
votes
1answer
59 views
Efficient traffic allocation
Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the ...
0
votes
0answers
110 views
Gas Station Problem Variation
My friend challenged me with this question. I've enjoyed two weeks with ocassional problem-solving sessions but it became such bug in my head that I needed to sign up :)
We have:
car with fuel ...
0
votes
0answers
32 views
Algorithm to check if exists a valid streaming sequence in O(n)?
Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
1
vote
0answers
53 views
Is there any greedy solution for bitonic tour
I have found dynamic solution for Bitonic tour but I could not find any greedy approach for this problem. Is it possible to solve it in a greedy manner?
2
votes
1answer
66 views
Activity Selection and Matroid Theory
Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.
I was trying to understand this. So far, I was ...
1
vote
1answer
544 views
How does the nearest insertion heuristic for TSP work?
In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson ...
0
votes
2answers
73 views
Greedy Heuristic for the Traveling Salesperson Problem
We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any ...
3
votes
1answer
320 views
Find the minimum set of intervals for given set of numbers
For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$
the answer is $${\{[1....
1
vote
1answer
47 views
What do we call a greedy algorithm that tracks the best $n > 1$ solutions?
A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.
To avoid this problem, we may keep track of the best $n > 1$ ...
1
vote
2answers
61 views
Online set filling with redistributions
Edited: Suppose we have 4 sets $A, B, C, D $ which can can hold a maximum of two elements, each.
Now, elements ($E_i$) arrive serially with properties such as:
...
1
vote
0answers
78 views
Algorythm for creating Number-Rows
Given is a list of numbers.
Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is ...
