Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
423
questions
1
vote
1
answer
23
views
Comparing a greedy and a brute force algorithm for NMS
Hello I am trying to implement Non Max suppression algorithm for removing overlapping bounding boxes. I have a list of bounding detected by an object detector in the format B(x,y,w,h,s)
x,y are ...
-1
votes
2
answers
55
views
Given m intervals and an array of integers, your task is to minimize the number of operations in which you can make the elements of the array nonposit
You are given the number $m$ and $m$ intervals of the form $a_i, b_i, v_i$, where $a_i<=b_i$ and $v_i>0$ and also a number $n$ and an array $s$ of length $n$, where $s_i>0$. In one operation ...
- 1
0
votes
0
answers
40
views
Why is the solution to Cinema Seat Allocation considered greedy?
LeetCode problem 1386. Cinema Seat Allocation requires finding the number of 4-person seating groups available (subject to certain constraints) after individual seat reservations have been made. The ...
- 1,548
0
votes
1
answer
68
views
Proving the correctness of a greedy algorithm for the Circular Scheduling Problem
Consider the following variation on the Interval Scheduling Problem
You have a processor that can operate 24 hours a day, every day. People
submit requests to run daily jobs on the processor. Each ...
0
votes
0
answers
16
views
Is this Greedy Search or Uniform Cost Search?
In the below Image, S is the starting point and E is the end point.
Image link
Now, the Title of the video says that its a Greedy Best First Search.
However, while browsing stackoverflow, I came ...
- 1
1
vote
1
answer
59
views
Proving a greedy algorithm of finding MINIMAL group
I am given a group $A$ of real numbers and I have to find the minimal group $B$ such that for each $a$ in $A$ there exists at least one $b$ in $B$ such that $|a-b|\leq 1$
So what I think the algorithm ...
- 13
1
vote
1
answer
42
views
Greedy algorithms criterion/ intution
Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
- 113
1
vote
1
answer
75
views
First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2
Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total ...
0
votes
0
answers
24
views
Optimality in greedy task
There is a well-known problem of the best time to buy and sell stock. Assume now we have two arrays, SELL and BUY. Each time SELL[i] > BUY[i]. Assume we have initial budget B, and we can buy any ...
- 151
0
votes
1
answer
56
views
How to cover elements with minimum amount of elements
I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem.
I have elements from 1 to n and I am trying to cover all of the elements using the ...
- 11
-2
votes
1
answer
60
views
What would be an efficient algorithm that finds the maximum number of party people?
You want to organize a party and invite as many of your N friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be ...
user160756
3
votes
1
answer
109
views
Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem
The following problem statement is given:
Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. ...
- 43
3
votes
1
answer
157
views
Maximum Independent Set of a Tree using Greedy Algorithm
I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph?
...
- 31
0
votes
0
answers
27
views
How an assignment problem is solved using greedy heuristic algorithm
Consider small instance of GAP involving 5 items and 2 resources with capacities 5 and 12 respectively. If we have cost matrix Cij and also consumption matrix bij with jobs vs resources, how can we ...
0
votes
0
answers
33
views
Finding the Optimal Palette for a Set of Images
Motivation
I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
- 1
0
votes
1
answer
35
views
Workers with certain strength carrying boxes. (Greedy)
I just had an algorithms exam and had the following problem:
Supposed there are $n$ workers and $n$ objects. Each worker has a strength, $s_i$ and each object has a weight $w_i$. Each worker needs to ...
- 1
1
vote
0
answers
41
views
prove the correctness of greedy algorithm on interger optimize
Let $n$ and $r$ be positive integers. For i = 1,2,...,n, let $f_i$ be a univariate real-valued function defined in the integer domain and let $f_i(x_i)$ be $-\infty$ for negative integer $x_i$.
Any ...
- 193
1
vote
1
answer
48
views
How to generate all possible colour vectors generated by greedy colouring on a graph?
Given a graph $G$, how can we generate all possible color vectors that could be generated via greedy coloring?
N.B. Greedy coloring takes a graph and an order of vertices. It traverses vertices ...
- 298
2
votes
2
answers
505
views
Select a subset of k intervals which form maximum length if we take union of these k intervals
Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals.
Note that there are 2 cases ...
- 123
0
votes
0
answers
64
views
proof that the longest processing time rule computes an optimal schedule
I want to prove that:
Theorem 2.8: For any input to the problem of minimizing the makespan on identical parallel machines for which the processing requirement of each job is more than one-third the ...
- 29
1
vote
4
answers
277
views
Prove optimality of greedy strategy for fewest number of stops
Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since ...
- 117
0
votes
0
answers
98
views
Compute the schedule which gives the maximum number of points
Here is the problem statement. Let $E_1,...,E_n$ be a set of $n$ exercises, each taking 1 day to solve, and suppose we have $n$ days available to solve the exercises. Each exercise $E_i$ has a ...
- 117
1
vote
1
answer
83
views
Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?
The following approximation algorithm for the Minimal Dominating Set Problem is said by a fellow student to be a 1.5-approximation:
Start with empty set $S$
As long as not all vertices are covered:
...
- 13
2
votes
1
answer
115
views
Dynamic programming: optimal order to answer questions to score the maximum expected marks
You have $n$ questions in an exam. Question $i$ is answered correctly with probability $p_i > 0$. If question $i$ is answered correctly, you get $R_i$ marks. You can choose to answer
the questions ...
- 23
1
vote
1
answer
62
views
Scheduling jobs with two people where part (a) of each job must be finished before part (b)
There are n jobs each consisting of two parts: a and b.
There are two people:
person ...
- 23
4
votes
1
answer
168
views
Possibly Tractable Variation of Suguru Puzzles
I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
- 43
0
votes
0
answers
39
views
Is there always a Dynamic Programming Solution underlying a greedy solution to any algorithmic problem?
According to CLRS book, Introduction to Algorithms,
Nevertheless, beneath every greedy algorithm, there is almost always a
more cumbersome dynamic-programming solution
As the word "almost" ...
0
votes
1
answer
86
views
Greedy Algorithm for Geometric Set Cover
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.
The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
- 53
2
votes
2
answers
87
views
Greedy algorithm-maximal minimum average of n pairs
Lets assume $2n $ gifts such that each gift $i$ has price $a_i$
The goal is to find a partition of the gifts into $n$ pairs such that each pair $P_i=\left(a_{i_{0}},a_{i_{1}}\right)$ has maximal ...
- 232
1
vote
0
answers
52
views
Find the smallest Valeriepieris circle
The Valeriepieris Circle is a circle within which it is supposed that the majority of the World's population lives. I'm interested in general-case and average-case algorithms for finding such a circle....
- 133
1
vote
0
answers
18
views
Optimal expression ordering with short-circuit evaluation [duplicate]
Let $E_1, E_2, \ldots, E_n$ be boolean-valued expressions, each with an associated evaluation cost and probability of returning true. For simplicity, assume these ...
- 105
0
votes
0
answers
53
views
Finding the diameter of a N-ary tree graph, without using BFS
As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph.
This must be done in linear time.
The problem states that the graph is undirected ...
- 315
1
vote
1
answer
624
views
Minimal number of positive intervals to cover all positive elements
I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray&...
- 315
0
votes
1
answer
44
views
Maximal Profit of 'legal' cutting of a board
I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill.
Given a board of length $n$, and an increasing ...
- 315
1
vote
0
answers
19
views
Randomly Split a Bar Into Beats
So I'm writing a software that generates random MIDI tracks based on a given mode, tonal etc.
As for now the randomisation works on tones building sequences of equal duration.
What I'd like to do is ...
- 111
0
votes
0
answers
31
views
Maximum Accumulated Balance after Purchasing Machines
A company is able to earn x dollars per day without any machines. However, there are n machines available for purchase. The <...
- 11
0
votes
0
answers
78
views
Proving that a greedy algorithm is correct using an exchange argument
I am trying to make a greedy algorithm for filling boxes. The rules are as follows:
1. Each box and item has an associated weight/capacity.
2. An item only fits into a box if its weight is less than ...
-2
votes
1
answer
30
views
Given x <= y, find a sum adding to y such that all elements are <= x and decreasing and the final element is maximised
Given $x \leq y$, find a sum $y_1+y_2+...+y_n$ where $y_i \leq x$ and $y_{i-1} \geq y_i$ for $1 \leq i \leq n$ and $y_n$ is maximised.
For example, given $x = 5$ and $y=17$, an optimal solution would ...
- 1
2
votes
1
answer
347
views
Dijkstra as a greedy algorithm
I'm preparing some material for students about greedy algorithms, and there is one point that confuses me: how Dijkstra's algorithm fits into the greedy framework.
I would like to say that we have ...
- 315
1
vote
0
answers
21
views
Stateless item distribution
I'm not sure if there's a name for this problem, but I'm hoping to validate my proposed solution or hear other ideas for solving it. This stems from a real engineering problem I've encountered at work,...
- 111
0
votes
0
answers
83
views
Complexity of fractional knapsack problem
I am bit confused while reading a standard textbook of my curriculum, where it is mention time complexity for knapsack problem is O(nlogn), and rationale they provided is we need O(n) to calculate (...
0
votes
1
answer
169
views
Is Huffman coding dynamic programming
Huffman coding follows a bottom-up approach where as Shannon-Fano coding is top-down. Is that contrast similar to dynamic programming versus greedy algorithm (dynamic programming always give optimal ...
- 163
0
votes
0
answers
98
views
Frontier steps for greedy best first search
I've been asked to list the frontier steps for greedy best-first search for the graph in the picture below.
I've attempted to recreate the algorithm in Golang, as shown below:
...
- 123
1
vote
1
answer
451
views
Proving that the greedy algorithm for job scheduling has a 2 - (1/m) approximation ratio
In the scheduling problem, the input is a sequence $T_1,T_2,...,T_n$ which are the times of $n$ jobs to be executed in m identical machines. A schedule is an assignment of the jobs to machines.
The ...
- 413
0
votes
1
answer
442
views
Optimal greedy algorithm solution for cell tower placement
Supose we have $n$ customers with interval that represent their range. For example, $[1,8], [2,5], [4,6], [1,9]$ for each customer. For a customer to have range coverage, a tower must be present ...
- 11
1
vote
1
answer
298
views
Formal Proof on why Greedy isn't working on one Particular Problem
Problem
You are given two integer arrays nums and multipliers of size n and ...
- 261
0
votes
0
answers
89
views
Is this how Interval Partitioning Problem aka interval graph coloring problem works?
You can refer the problem on later part of section 4.1 in "Algorithm Design Book by Jon Kleinberg and Éva Tardos"
Problem: We have "n" lectures and we our job is to assign all of ...
- 305
0
votes
2
answers
2k
views
Maximum subarray sum of given length range
Can anyone please help me solve this better than $O(|a-b| \cdot n)$?
Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having ...
- 53
-1
votes
1
answer
134
views
Largest number of disjoint paths of length $k$ and maximum reward in a tree
Consider exercise 23(c) of chapter "Greedy Algorithms", Algorithms by Jeff Erickson.
Given a tree $T=(V,E)$ in which each node has a reward, and
$k\in\mathbb{N}$, our goal is to find a set $...
- 267
0
votes
3
answers
2k
views
Greedy algorithm for postive interval covering
Consider the following problem from Jeff Erickson: Algorithms
that also appears in this post, which wants us to prove a lower bound for the problem.
Suppose you are given an array $A[1 .. n]$ of ...
- 267