Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
4 votes
2 answers
82 views

Finding optimal sequence of attacks to minimize number of soldiers needed

The problem Trying to improve my algorithms I bumped into a problem by Pedro Pablo Gómez Martín and Marco Antonio Gómez Martín, which I can summarise like this: You are given a list of enemy bases ...
user2891462's user avatar
0 votes
0 answers
87 views

Interval scheduling; sort by ending times

You have $n$ events on your calendar, defined as intervals with a start time $s_i$ and a finish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$...
Lipid's user avatar
  • 9
0 votes
0 answers
16 views

How does additional assumptions increase approximation factor?

I am studying the greedy algorithm for maximal weighted matching in arbitrary graphs. I have proven that this algorithm has approximation factor $\frac{1}{2}$. Assume now that the weights in the graph ...
mNugget's user avatar
  • 101
0 votes
0 answers
19 views

Proving Optimal Greedy Algorithms [duplicate]

How is the best way to go about proving that a greedy algorithm is optimal, inductive vs contradiction, are there parts in the proof that are key to include. I did not feel that the lesson I was ...
James's user avatar
  • 1
1 vote
1 answer
104 views

Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
FarsoFracico's user avatar
0 votes
2 answers
97 views

I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

How to learn DSA if you are already working as a software engineer and have decent knowledge about development. Only thing that makes me procratinate is going over theories behind different data ...
Hardik Dhuri's user avatar
1 vote
2 answers
126 views

Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by ...
Gary Drocella's user avatar
0 votes
1 answer
86 views

Visiting all nodes of a directed graph exactly once (not dfs)

Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should ...
vhd's user avatar
  • 45
1 vote
1 answer
89 views

Greedy Maximum Bipartite Matching

To find the maximum matching on a bipartite graph, I propose the following greedy algorithm: At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours ...
eeeeellllll's user avatar
0 votes
0 answers
33 views

Greedy algorithm for trading cryptocurrencies with perfect price information

Assume the following hypothetic scenario: You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
lafinur's user avatar
  • 181
0 votes
0 answers
87 views

Is the following a correct proof for the interval covering problem?

I have written the following greedy stays ahead proof for the problem of covering an interval with subintervals. Is it correct? I think it is, but this is my first time proving a greedy algorithm. ...
windoid's user avatar
1 vote
1 answer
137 views

Maximizing sum and product of an array

Given an array of positive numbers with allowed replication, what is the algorithm to find the max amount possible only with summing or multiplying elements? All numbers must be involved in some ...
vhd's user avatar
  • 45
3 votes
1 answer
96 views

On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty

On a table there are $n$ stacks (numbered $1$ to $n$). Stack $i$ contains $i$ tokens ($1 \leq i \leq n$). During a move, a set of stacks can be chosen and the same number of chips can be drawn from ...
John's user avatar
  • 31
0 votes
0 answers
24 views

Greedy algorithm for minimising the number of encountered obstacles from multiple start points to single endpoint in a grid

I am given a $N$ x $M$ sized grid and $K$ start points $S = (s_1, s_2, .. s_k)$ where each $s_k = (x_k,y_k)$ representing the position on the grid. I am also given a single endpoint $(x_{end}, y_{end})...
calveeen's user avatar
  • 141
0 votes
0 answers
81 views

Proof of The Optimality Of Greedy Algorithm for The Interval Scheduling Problem

I have this proof for the optimality of the greedy algorithm for the interval scheduling problem in my algorithms class, but I'm struggling to understand it fully, especially starting from the second ...
Mohamed Hendy's user avatar
1 vote
0 answers
59 views

Why do we need Optimal Substructure when proving the correctness of greedy algorithms

According to Introduction to Algorithms, to show the correctness of a greedy algorithm, we need to show: Greedy Choice Property (i.e. there exists one optimal solution that includes the greedy choice)...
SCLeo's user avatar
  • 111
1 vote
1 answer
61 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
66 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
72 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
411 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
23 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
64 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
52 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
119 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
29 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
86 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
69 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
195 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
446 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
62 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
35 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
37 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
43 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
51 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
655 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
313 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
2 votes
4 answers
697 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
  • 127
0 votes
0 answers
134 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
  • 127
1 vote
1 answer
104 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
136 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
79 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
184 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
1 answer
101 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
  • 63
2 votes
2 answers
126 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
55 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
19 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
64 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
  • 317
1 vote
1 answer
718 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
  • 317
0 votes
1 answer
56 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
  • 317
1 vote
0 answers
21 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

1
2 3 4 5
9