Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
232
questions
0
votes
0answers
9 views
Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general
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
15 views
Design a greedy algorithm by intermingling two sequences [duplicate]
I find myself solving problems for a test and the next problem I still can't solve it.
There are n ordered sequences, $S_1$ to $S_n$. It is requested to intermingling them to obtain a single sequence,...
1
vote
1answer
33 views
Minimize cost of recursive pairwise sums: how to prove the greedy solution works?
The problem is in this other question.
Why does this always work? It's not clear to me how one would use induction.
For $n = 3$, a quick calculation shows it works, however, I don't think it ...
2
votes
1answer
44 views
How do I minimize the cost of some algorithm that performs some operation on a list?
I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem ...
0
votes
2answers
41 views
largest subset of pairwise intersecting intervals [closed]
Given a set of intervals on the real line, compute the largest subset of pairwise
intersecting intervals (an interval in the subset must intersect with every other interval
in the subset). Design a ...
1
vote
1answer
35 views
Gas Station problem : Fixed path variation
Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path ...
3
votes
1answer
96 views
Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal
Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one.
A greedy algorithm for this would keep removing digits ...
1
vote
0answers
32 views
Take k numbers from the array and xor them with x to get maximum sum [duplicate]
Given an array A of n numbers and integers k and x. We can perform the following operation any number of times (including zero times). Take exactly k numbers from the array and replace each of them ...
2
votes
3answers
97 views
Selecting items from two arrays without duplicate indices to get maximum sum
Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you ...
2
votes
2answers
182 views
Split array into contiguous subarrays of approximately same sums
My question is similar to this splitting question, but my objective function is different.
Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty ...
0
votes
1answer
29 views
Difference between greedy and work conserving scheduler for DAG
For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do.
However, I found two different upper bounds on the computation time of $T$. For the ...
3
votes
2answers
49 views
Maximize number of museums visited in a day
Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day.
Suppose that no time is needed in ...
2
votes
1answer
47 views
What is an approximation factor for the Greedy Motif Search algorithm?
What is approximation factor for the Greedy Motif Search algorithm?
I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native ...
0
votes
0answers
40 views
Interval scheduling with shared resources between steps
I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each ...
2
votes
0answers
34 views
Heuristic for searching for solutions on an 8-puzzle variant with non-unique tiles
I'm trying to perform an A* search on a particular N-puzzle variant in which some tiles are identical. More specifically, assuming an $m \times m$ grid, there are m colors with m tiles of each. The ...
0
votes
1answer
104 views
Modified Knapsack Problem
I have a problem with the following optimisation problem:
In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, ...
2
votes
1answer
100 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
0
votes
0answers
87 views
Maximum matching blossom algorithm
https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf
Why do we use blossom contrast in maximum matching?
The examples that I have seen can easily be solved by just ...
0
votes
1answer
146 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 ...
0
votes
1answer
42 views
Proof for optimal interval scheduling using a Greedy Approach
You are given a set of n jobs, where each job j is associated with a size
s(how much time it takes to process the job) and a weight w(how important the
job is). Suppose you have only one machine ...
2
votes
1answer
84 views
Can a greedy algorithm have more than one subproblems to solve after making greedy choice?
For example:
s = <s1 s2 s3> is my problem,
I make greedy choice s2 and solve s1 and <...
1
vote
2answers
67 views
Putting as many items as possible with weight and size limit
I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice.
Any item has an item weight of Iw and item size of <...
2
votes
1answer
114 views
Greedy algorithm for even item distribution
I have this problem where I need to design a greedy algorithm. The problem is as follows:
A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $...
0
votes
0answers
24 views
Greedy Approach without constraint and a feasibility function
We know that the Greedy Approach in general, picks an element from a set of candidate elements that satisfies a predefined criteria (selection function) and is added to the solution if it satisfies ...
1
vote
1answer
96 views
Carpet into Box
Given a carpet of size a * b [length * breadth] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or ...
3
votes
1answer
91 views
Length of shortest codeword in Huffman encoding
Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1?
I thought of 2 cases where this ...
1
vote
1answer
35 views
Minimum Spanning Tree with one particular edge minimised(continued)
I have recently encountered a coding problem, specifically, the CCC problem S4.
In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
1
vote
2answers
59 views
Minimum spanning tree such that one edge can be minimised
During a computer coding exam, I have encountered such a problem.
Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
3
votes
2answers
163 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
1answer
46 views
Trying to understand the question(well spaced points ?) better
Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
0
votes
1answer
323 views
Is my proof of my greedy algorithm to find subsequence correct?
Credit to KleinBerg and Taros Book
Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
-2
votes
1answer
53 views
Number Theory Problem from Local Selection Contest EPFL | ETHZ
This was a question from the 2016 local (selection) contest in ETHZ, You have a high-precision alarm clock with three operations:
1) reset wake-up time to midnight (00:00:00.000000)
2) modify the ...
2
votes
1answer
66 views
Greedy Solution for Selecting Prefix Sum
Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to ...
0
votes
0answers
36 views
findining the smallest sum of squared lengths of the intervals I_{k}
Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals
$I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
2
votes
4answers
316 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
61 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
272 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
203 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
77 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
31 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
84 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
52 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
302 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
170 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
205 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
60 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
vote
1answer
123 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
79 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
252 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
175 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, ...
