Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
1
vote
0answers
22 views
Take k numbers from the array and xor them with x to get maximum sum
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
1answer
35 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
90 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
0answers
37 views
Greedy algorithm correctness
I'm trying to solve the following problem:
CEO is checking on it's employees at a constant times every day (for
an example the number of minutes after a shift started> {5, 35,
120..}). ...
0
votes
1answer
27 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 ...
2
votes
2answers
44 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
44 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
37 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
32 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
91 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
64 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
0
votes
0answers
79 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
120 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
37 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
80 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
97 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
46 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
81 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
34 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
56 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
105 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
297 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
51 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
63 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
34 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
256 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
60 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
241 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
149 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
63 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
83 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
51 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
268 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
147 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
190 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
57 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
105 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
72 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
230 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
162 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
108 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
85 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
207 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
325 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
926 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
75 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 ...
