Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
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 ...
Tanya Choudhary's user avatar
-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 ...
John's user avatar
  • 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 ...
Ellen Spertus's user avatar
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 ...
Tejas Anand's user avatar
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 ...
whoAsked's user avatar
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 ...
SpaceNugget's user avatar
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 ...
green_32's user avatar
  • 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 ...
TheCollegeStudent's user avatar
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 ...
openspace's user avatar
  • 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 ...
Ally Zane's user avatar
-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 ...
user avatar
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$. ...
asparagus's user avatar
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? ...
wamengti's user avatar
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 ...
Sai chand Gogisetty's user avatar
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 ...
yannick's user avatar
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 ...
Aidan's user avatar
  • 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 ...
AsukaMinato's user avatar
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 ...
Subhankar Ghosal's user avatar
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 ...
Kitwradr's user avatar
  • 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 ...
hah's user avatar
  • 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 ...
prcssngnr's user avatar
  • 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 ...
prcssngnr's user avatar
  • 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: ...
LostReminder's user avatar
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 ...
maynis's user avatar
  • 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 ...
AustinBest's user avatar
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 ...
Inteurce's user avatar
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" ...
Divyanshu Dwivedi's user avatar
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 ...
Sandra's user avatar
  • 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 ...
Danny Blozrov's user avatar
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....
lmonninger's user avatar
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 ...
Tavian Barnes's user avatar
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 ...
Aishgadol's user avatar
  • 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&...
Aishgadol's user avatar
  • 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 ...
Aishgadol's user avatar
  • 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 ...
Carlo Moretti's user avatar
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 <...
XYZ's user avatar
  • 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 ...
Bradley Lund's user avatar
-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 ...
Foxx's user avatar
  • 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 ...
Dmitry's user avatar
  • 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,...
Vincent's user avatar
  • 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 (...
Niraj Jain's user avatar
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 ...
Sam's user avatar
  • 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: ...
Ewan Valentine's user avatar
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 ...
SVMteamsTool's user avatar
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 ...
Andrew Kim's user avatar
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 ...
Rohit Singh's user avatar
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 ...
Pratik Hadawale's user avatar
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 ...
Iris's user avatar
  • 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 $...
ErroR's user avatar
  • 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 ...
ErroR's user avatar
  • 267

1
2 3 4 5
9