# Questions tagged [greedy-algorithms]

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

423 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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 ...
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 ...
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 vote
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 ...
1 vote
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 ...
1 vote
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 ...
24 views

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 ...
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 ...
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 ... 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$. ...
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? ...
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 ...
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 ...
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 vote
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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: ...
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 ...
1 vote
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 ...
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 ...
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" ...
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 ...
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 ...
1 vote
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....
1 vote
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 ...
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 ...
1 vote
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&...
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 ...
1 vote
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 ...
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 <...
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 ...
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 ...
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 ...
1 vote
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,...
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 (...
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 ...
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: ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...