Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
235
questions
0
votes
0answers
29 views
Improving on Monte-Carlo
Can I improve on a Monte-Carlo search for the problem, described?
So I have a graph/network consisting of segments a1, a2, ..., b1, b2, ..., and c1, c2, ...
For all the underlying segments there is ...
2
votes
0answers
28 views
Interval partitioning problem different approach - arrange lectures in minimum number of classrooms
The problem of scheduling lectures in minimum number of classrooms is as follows:
Find minimum number of classrooms to schedule all lecture so that no two occur at the same time in the same room.
The ...
3
votes
1answer
49 views
Greedy Heuristics with an Altered Subset Sum/Partition Problem
Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, ...
0
votes
0answers
19 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
20 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
46 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
50 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
46 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 ...
2
votes
1answer
66 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
105 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
33 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
187 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
495 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
33 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
59 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
49 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
43 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
35 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
117 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
135 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
0
votes
0answers
91 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
170 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
50 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
90 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
70 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
141 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
27 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
115 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
116 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
37 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
62 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
193 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
50 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
452 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
59 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
67 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
431 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
67 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
320 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
288 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
102 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
33 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
87 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
54 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
345 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
202 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
224 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
62 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
152 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 ...
