Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
260
questions
3
votes
2answers
49 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 ...
0
votes
1answer
21 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
21 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
61 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
68 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 ...
2
votes
1answer
33 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
14 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
61 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 ...
6
votes
0answers
140 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 ...
1
vote
1answer
39 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
32 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 ...
0
votes
2answers
101 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
125 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 ...
1
vote
1answer
146 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$)...
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
61 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
37 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
44 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
47 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 ...
0
votes
0answers
84 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?
...
2
votes
1answer
75 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
54 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 ...
3
votes
1answer
78 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, ...
1
vote
1answer
22 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
60 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
90 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
35 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
21 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
61 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
51 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
51 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
126 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
117 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
491 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
1k 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
59 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
69 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
54 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
45 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
37 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
131 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
204 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
0
votes
0answers
112 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
270 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
63 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
105 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
74 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 <...
