Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
269
questions
1
vote
1answer
24 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
30 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
30 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 ...
7
votes
1answer
317 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')$ ...
0
votes
0answers
19 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
25 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
44 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
187 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
70 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 ...
0
votes
0answers
32 views
Catching ball - finding the maximum number of caught balls
I'm attempting to solve the following problem:
Balls are falling from the sky. We know at which location (on a
straight line) will each ball drop, and we know the time (in seconds)
at which ...
9
votes
2answers
3k views
Knapsack Greedy Approximation: Worst Case
I am currently studying approximation algorithms and I have run into an issue with a study problem.
The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, ...
2
votes
1answer
342 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, ...
4
votes
1answer
255 views
Single machine job scheduling to minimize weighted sum of completion time
Given $n$ jobs, schedule them such that the weighted sum is minimum.
weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :
$S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
0
votes
2answers
520 views
Will a Greedy algorithm give a correct result for minimum partition?
Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?
Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now ...
3
votes
2answers
60 views
Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges?
We have a set of $n$ products, each $i$th product can be kept in a
temperature between $c_i$ and $h_i$.
We have to buy fewest number of fridges for these products. The
fridges can only have ...
1
vote
2answers
1k views
How to prove greedy algorithm for number partitioning?
the partition problem (or number partitioning1) is the task of
deciding whether a given multiset S of positive integers can be
partitioned into two subsets S1 and S2 such that the sum of the
...
0
votes
1answer
28 views
Minimum total waiting time for arrivals/durations
I have come up with the following problem, and cannot seem to find an effective way of solving it:
Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration ...
2
votes
0answers
22 views
Optimal strategy for tossing three dependent coins
Suppose that I have three correlated coins. The marginal probability of Head of coin $i$ is denoted by $p_i$.
The conditional probability of head for coin $i$ given the outcomes of coin $j$ and $k$ ...
1
vote
3answers
75 views
How can I prove that my greedy algorithm for least guards is optimal?
This is the problem:
An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
0
votes
0answers
109 views
Making Candies - HackerRank question - proof of optimality of a greedy approach
I stumbled across this question in HackerRank:
Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies.
Karl just started a ...
0
votes
1answer
77 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 ...
6
votes
0answers
145 views
Correctness of a greedy Algorithm on Knockout Tournaments
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
2
votes
1answer
36 views
Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time
We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is ...
0
votes
0answers
16 views
How to detect self loop in graph using greedy algorithm if given list of number of degrees
if you are given list of n integers that represents the degree of a graph. How to detect if there self loop in the graph using greedy algorithm.
0
votes
3answers
74 views
Optimality of a Greedy Algorithm
If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you ...
1
vote
1answer
45 views
Maximum number of similar groups of a given size that can be made from a given array
I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.
I need to find the maximum number of groups with the ...
0
votes
0answers
44 views
Job Scheduling with deadline with $nlogn$ algorithm
We know that there is a Greedy algorithm for scheduling of $n$ jobs which each job has its own deadline and profit.
In greedy algorithm, we sort the set by their profit descendant, And if a job can ...
2
votes
1answer
229 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
1
vote
2answers
185 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 ...
0
votes
1answer
313 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
1answer
155 views
Selecting elements from two arrays to get a target sum
Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.
Design an algorithm to solve the following problem.
For each index $i$ ($1\leq i \leq n$)...
4
votes
1answer
247 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 ...
0
votes
2answers
269 views
Why this greedy algorithm fails in rod cutting problem?
Recall the rod cutting problem.
Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and ...
2
votes
2answers
201 views
Knapsack with a fixed number of weights
Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There ...
2
votes
1answer
37 views
Determine aproximation factor in a greedy algorithm
Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences.
We want to choose a menu such that we minimize the cost and ...
1
vote
0answers
64 views
Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem
The unweighted maximum coverage problem is defined as follows:
Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$.
Objective: find a subset $S' \subseteq S$ such ...
1
vote
0answers
39 views
Weighted Activity Selection Problem with allowing shifting starting time
I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists.
In my case, I am allowed to ...
-1
votes
1answer
50 views
You have K amoebas and one amoeba can divide into A,B,C amoebas after one instruction then find the minimum no. of instruction to have N amoebas
. You have developed an artificial amoeba, and you can control exactly how it divides.
Each individual amoeba can be instructed to divide into A, B, or C amoebas. That
is, if you instruct an amoeba to ...
0
votes
0answers
23 views
Activity Selection with changable start time
I have been studying a problem in my work and I have reduced my problem to likewise Activity Selection problem. It is a problem that I know and I am familiar with the greedy solution.
However, in my ...
0
votes
1answer
48 views
Schedule each entree so that all entrees are completed in the shortest amount of time
Lets say we have plenty people to dress up entrees, but only one chef to cook them. Each entree $E_i$, takes $c_i$ time to cook and $d_i$ time to "dress up". The dressing up of entrees can occur while ...
1
vote
3answers
864 views
Stable matching problem is greedy or Dynamic?
Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.
0
votes
0answers
115 views
How does ordering paradigm differs from subset paradigm in greedy method?
What is the difference between subset paradigm and ordering paradigm of greedy method approaches?
More precisely I didn't understood how does the ordering paradigm differs from subset paradigm?
...
3
votes
1answer
80 views
Optimal solution for Weighted points problem
Problem:
Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, ...
2
votes
1answer
103 views
Hitting Set Problem with non-minimal Greedy Algorithm
The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
1
vote
1answer
57 views
Converting a greedy algorithm to a dynamic programming algorithm
Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:
First, find a maximum indpendent set of ...
1
vote
1answer
25 views
Trivial solution to the Continuous Knapsack problem
I am a bit puzzled as to why the continuous knapsack problem is a non-trivial problem
https://en.m.wikipedia.org/wiki/Continuous_knapsack_problem
Using the terminology in the Wikipedia link above,
...
0
votes
0answers
37 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
64 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
107 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, ...
4
votes
1answer
487 views
2 approximation algorithm for the single machine scheduling problem
We are given one machine and $n$ jobs that we want to process.
For the $n$ jobs we have the following data:
$r_{1}, ... , r_{n}$ are the release times
$p_{1}, ... , p_{n}$ are the processing times
...
