Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
383
questions
1
vote
1
answer
48
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 ...
- 203
0
votes
0
answers
19
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 ...
0
votes
2
answers
85
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 ...
- 35
-1
votes
1
answer
63
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 $...
- 1
0
votes
1
answer
29
views
Greedy algorithm for postive interval covering
Consider this problem from Jeff Erickson Algorithm
that already in this site, there is a this post about it where it want us prove a lower bound for it.
The question is:
Suppose you are given an ...
- 1
0
votes
1
answer
33
views
Tweaking Floyd-Warshall Algorithm to detect cycles
Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that ...
0
votes
1
answer
95
views
Find largest number of disjoint paths with lenght $k$ in a tree
Consider this problem from Jeff book
Given a rooted tree $T$ and an integer $k$ as input, and it should
compute the largest possible number of disjoint paths in $T$ , where
each path has length $k$. ...
- 1
2
votes
1
answer
73
views
Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct
This problem is from LeetCode.
You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k ...
- 1
0
votes
0
answers
68
views
Is this greedy algorithm optimal?
Let $T=(V,E)$ be a tree and let $k$ be a natural number. The problem is to find the largest set of vertices $S \subseteq V$ such that $(*)$ every path in $T$ consists of at most $k$ vertices from $S$.
...
- 13
3
votes
1
answer
148
views
Greedy filling unit intervals
I have unit intervals given such as $I = \{\{s_1, s_1 + 1\}, ..., \{s_k, s_k+1\}\}$ ($\forall s_i \in \mathbb{R}$). I am given a list of $X$ reals, such that each of the reals belongs to at least one ...
- 149
2
votes
1
answer
72
views
Does this greedy algorithm minimize the sum of the diameters of two clusters?
Suppose given $2n$ points in the plane and we want to partition points into two clusters $C_1$ , $C_2$ such that each cluster contains exactly $n$ points and we want to minimize the sum of the ...
- 1
1
vote
0
answers
34
views
Proving the least number of operators required equals $min((x-target)*2, (target*2)-1)$
Here is the source for the problem below: https://leetcode.com/problems/least-operators-to-express-number/discuss/1675169/java-or-recursion-or-greedy-or-math
For completeness, below is the problem ...
- 1
0
votes
1
answer
76
views
Is there a solution faster than O(n^2) for this greedy/sorting problem?
In a market there are N different items where each item is unique and identified by id (1-N). There are also K buyers with names (1-K). Each buyer has 2 items that they want to buy (A, B), where A is ...
- 21
1
vote
2
answers
191
views
finding a greedy algorithm that maximizes total energy of fruits subject to expiry dates
This problem is based off of the following problem on stack overflow: https://stackoverflow.com/questions/64797299/greedy-algorithm-to-maximize-score. The second answer is incorrect because the ...
- 101
4
votes
1
answer
137
views
Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?
Given a multiset $S$ of numbers, partition it into two subsets $S_1 $ and $S_2$.
How to maximize the sum of their medians? For example, the median of {1,2} is ...
- 177
1
vote
0
answers
65
views
Graph in which greedy algorithm for maximum matching is a 2-approximation
Here is a greedy algorithm for maximum bipartite matching:
Iteratively select an edge that is not incident to previously selected edges.
This algorithm returns a 2-approximation, and runs in linear ...
- 111
0
votes
0
answers
30
views
Find set of vertices of max size under some restrictions [duplicate]
I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question.
Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
- 191
0
votes
1
answer
81
views
Find most vertices in a directed tree where no path of length less than 3 connects any pair
Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of ...
- 191
1
vote
0
answers
64
views
Is the optimal substructure property necessary to guarantee the existence of a greedy algorithm that always finds the optimal result?
I'm trying to understand what is necessary to guarantee that a problem has a greedy algorithm that always produces optimal solutions.
In multiple places I find that a greedy algorithm can be ...
- 111
1
vote
1
answer
38
views
Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?
A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most ...
2
votes
1
answer
211
views
Greedy Stays Ahead proof of "Jump Game"
(Source: https://leetcode.com/problems/jump-game-ii/)
Consider the following problem: Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each ...
- 151
2
votes
1
answer
34
views
Optimal order to minimise time until first success
Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t_i$ time to talk to and there is $p_i$ probability to make the sale to that customer - ...
- 23
5
votes
0
answers
116
views
discrete optimization problem with a matrix inverse
I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$
$$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
- 51
0
votes
1
answer
79
views
Maximum number of teams that can be formed with given age such that the sum of their age is more than 18
An array of students age is given : $ A = \{ A_1,A_2, ..., A_n \} $. Form maximum number of teams such that the sum of age for each team is more than 18. Note that each team consists of only 2 people.
...
2
votes
2
answers
114
views
Given n positive integers, pick two elements and subtract each by one with one operation. Find max operations
Problem Description: we have an array of n positive integers and in one operation we have to choose two elements in the array and decrease them by 1. (Elements on which we are performing this ...
- 21
0
votes
0
answers
30
views
Why can we solve this problem by a greedy algorithm?
https://atcoder.jp/contests/past202004-open/tasks/past202004_f
I am trying to solve the following problem:
We have $N$ tasks. Let today be Day $1$. You can do the $i$-th task on or after Day $A_i$, ...
- 111
3
votes
2
answers
196
views
Algorithm that finds a matrix with a specific number of 1s in its rows & columns
Question:
Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...
- 41
2
votes
1
answer
79
views
Determines the smallest set of unit-length closed intervals that contains all of the given points
Question: Describe an efficient algorithm that, given a set $\{x1, \cdots, x_n\}$ of points on the real line, determines the smallest set of unit-length closed intervals that contains
all of the given ...
- 459
1
vote
1
answer
42
views
The preliminary of the Bandit Gradient Algorithm
In the papers introducing The Bandit Gradient Algorithm as Stochastic Gradient Ascent, the following relationship:
is always considered as a preliminary and lacks proof for it. Does anyone know how ...
- 51
0
votes
0
answers
58
views
Optimal Word Guessing Algorithm in $O(n \log n)$
Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been ...
- 13
1
vote
0
answers
29
views
Social Networking Disease Transmission
You are given an undirected graph (social network) in which each edge $e = (v, v')$ has an interval $I_e = [l_e, u_e]$ on it. The meaning is that you know that $v$ and $v'$
met at some point during ...
- 23
0
votes
1
answer
58
views
Bin packing problem and optimality proof
Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w_i\in W$ is stored before $w_j\in W$ then ...
- 115
0
votes
1
answer
110
views
Time-varying edge cost Minimum Spaning Tree
I am having a hard time wrapping my head around the time-varying edge cost of this question :
Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
- 3
2
votes
1
answer
54
views
Why is this greedy strategy always correct for this problem?
I'm trying to solve the following problem: https://cses.fi/problemset/task/1084/
My first idea to solve this was to sort the applicants and apartments in increasing order. Then, I iterate through all ...
- 123
0
votes
1
answer
58
views
Greedy approach behind SPOJ Aggressive Cows problem
My doubt is related to the given SPOJ problem:
Farmer John has built a new long barn, with N (2 <= N <= 100,000)
stalls. The stalls are located along a straight line at positions
x1,...,xN (0 &...
0
votes
0
answers
75
views
Gas Station problem proof
I'm trying to prove the solution for the problem Gas Station (LeetCode 134)
Let's define $d_i$ to be the difference $g_i - c_i$.
Basically it's a greedy solution where you look for the first $k$ s.t.
$...
- 377
0
votes
0
answers
73
views
Sequential Tasks with Greedy Algorithm
We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be ...
- 23
0
votes
0
answers
116
views
A Variant to "Boats to Save People"
This question is a variant of LeetCode 881. Boats to Save People by removing the restriction of "each boat carries at most two people at the same time" from the original question.
Problem ...
- 1,071
-1
votes
1
answer
54
views
Proving correctness for greedy algorithm in string removal problem
Problem Statement:
You are given a string s and two integers x and y. You can perform two types of operations any number of times.
Remove substring "ab" and gain x points.
For example, when ...
- 39
0
votes
0
answers
35
views
Sum optimization and greedy approach
I've came across the optimization bellow
$\phi=argmin_{\theta} \displaystyle\sum_{i=1}^{N}f(x_i,\theta)$
Can i say that minimizing this summation by minimizing each term $\left(\displaystyle\frac{df(...
- 101
0
votes
1
answer
216
views
How to determine the approximation factor for greedy vertex cover algorithm?
The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $0$ are left.
Formally:
$\text{GreedyVertexCover}...
- 282
7
votes
0
answers
91
views
Optimality of DSATUR on interval graphs
The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different ...
- 6,942
1
vote
1
answer
249
views
Minimal number of intervals that covers $\{1,...,k\}$
Let $F$ be a family of sets of consecutive integers in $\{1,…,k\}$ that is closed under taking subintervals, i.e. for any $a≤b≤c≤d$, if $\{a,…,d\} \in F$, then $\{b,…,c\} \in F$ also. Find a minimum ...
- 13
3
votes
0
answers
39
views
Equalizing level of water in glasses problem
I have a problem on my hands, and would like help matching it to the existing, studied problems. I explain it like so:
I have a sequence of $n$ equal-sized glasses of water. Each has a different ...
-1
votes
1
answer
42
views
Fitting arrays into RAM algorithm question
We'll consider the RAM as a sequence of cells that can contain data. Some cells already contain some data, some are empty. The empty cells form the so-called memory clusters. Thus, a memory cluster is ...
- 143
3
votes
1
answer
142
views
Partition of a $k$-partite graph to minimal number of connected sets
Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices.
I'm trying to partition the graph to the minimal number of connected sets.
Sets $A_0, ...
- 23
1
vote
0
answers
55
views
Finding an optimal solution for the following problem
This is an intriguing question given by my friend for which I want to find an optimal solution:
Each week, you can choose to work ONLINE $(ON)$ or in person $(WR)$ in
your department's office. If you ...
- 341
0
votes
0
answers
426
views
Minimum Number of Refueling Stops with Dynamic Programming
This is a question from Leetcode and I wanted to solve it with Dynamic Programming. upon seeing the solution, I am not able to get the intuition behind the logic. I was able to understand the solution ...
- 159
1
vote
0
answers
21
views
Time to form a complete graph from n vertices given that only k vertices can be used at a time [closed]
I know this problem is related to the greedy algorithm and max edges incomplete graph but can't come up with a solution.
Problem
You are given two numbers n and k:
n >= k
n is the total # of ...
- 111
0
votes
1
answer
154
views
How to prove the my greedy algorithm for placing guards?
Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images ...
- 13