Questions tagged [greedy-algorithms]

Questions about algorithms that make at each step the locally optimal choice.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5 6