Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
110 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 ...
1
vote
0answers
32 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 ...
0
votes
0answers
27 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 ...
0
votes
1answer
70 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 ...
1
vote
0answers
25 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 ...
1
vote
1answer
33 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
1answer
113 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 ...
2
votes
1answer
33 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 - ...
5
votes
0answers
111 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} ...
0
votes
1answer
49 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
2answers
73 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 ...
0
votes
0answers
28 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$, ...
3
votes
2answers
95 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 ...
2
votes
1answer
47 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 ...
1
vote
1answer
33 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 ...
0
votes
0answers
52 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 ...
1
vote
0answers
28 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 ...
0
votes
1answer
51 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 ...
0
votes
1answer
107 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 ...
2
votes
1answer
52 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 ...
0
votes
1answer
48 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
0answers
49 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. $...
0
votes
0answers
58 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 ...
0
votes
0answers
48 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
votes
1answer
34 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 ...
0
votes
0answers
34 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(...
0
votes
1answer
132 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}...
7
votes
0answers
84 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 ...
1
vote
1answer
55 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 ...
3
votes
0answers
36 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
1answer
41 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 ...
3
votes
1answer
137 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, ...
1
vote
0answers
48 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 ...
0
votes
0answers
306 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 ...
1
vote
0answers
20 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 ...
0
votes
1answer
114 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 ...
0
votes
0answers
57 views

Filling Two Knapsacks with greedy algorithm

I've got the next problem, where I have two, instead of one, knapsacks. Formally, we have items $1, \ldots , n$ and each item $i$ has a positive integer weight $w_i \in \mathbb{N}$ and a positive ...
1
vote
3answers
70 views

Greedy Algorithm: Optimal Substructure

I don't have a CS degree but I have recently taken up studying algorithms very seriously. I have been studying greedy and dynamic programming for days and I come across the below definition a lot, ...
0
votes
0answers
36 views

Is correctness implied by an optimality proof?

New to proofs (in the context of analysis of algorithms). I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
0
votes
0answers
83 views

Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem. I understand how the solution is implemented but,...
2
votes
0answers
52 views

Which algorithms exhibits Greedy Choice Property but not Optimal Substructure Property

After a few courses using CLRS, I still have not been able to find a satisfying answer to the title question. This answer suggests Hoffman trees. But here the greedy choice is the two subtrees with ...
-1
votes
1answer
181 views

Proof of Correctness : Arranging the sheep

I've come across a question in Codeforces contest 719(Div - 3). The problem goes like this : I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
0
votes
0answers
47 views

maximal independent set on grid-based graph proof of approximation ratio

We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight. We use a greedy algorithm that takes in each step maximum weighted ...
2
votes
1answer
25 views

Optimize stacking time series by offsetting start times (feels like a backpack problem?)

Given a time-series of data collected from a single running process that takes 8 hours to complete: Minute GB of Disk Space Used 0 0 1 8 2 15 3 22 ...Etc. It is sampled every minute, for 8 ...
1
vote
1answer
68 views

Find the minimum cost of adding the elements of a set (greedy algorithm)

I'm VERY stuck with this problem: Given a set (with possible repeated elements), the cost of adding two elements $x, y$ is $x + y$. For example, the possible costs of the next set $\{1,2,5 \}$ are: ...
3
votes
1answer
48 views

Expected behavior of an algorithm to minimize rankings

Suppose $n$ students have preferences over $n$ different notebooks. Their preferences can be represented with a square matrix of size $n$ where each column is a different permutation of the vector $[1:...
1
vote
1answer
26 views

Greedy approach suggestions for assigning objects

Suppose there are three categories of people. Type X, Type Y, Type Z. In each type, there are two objects of subtype Type 'a' and type 'b'. For example. X: a1 , a2 , b1 , b2 Y: a3 , a4 , b3 , b4 Z: a5 ...
2
votes
1answer
68 views

k-center problem: proof for Gon algorithm gives a 2-approximation

The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following ...
1
vote
1answer
108 views

Find minimum number of points which intersect overlapping arcs

Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time. I'm having some trouble proving ...
1
vote
1answer
43 views

Does any graph based optimization problem, which have a greedy algorithm, has guarantee that there exist an order which give the optimum

There exist greedy algorithms for vertex coloring like optimization problems. We know that for graph coloring, there is an order of vertices for which greedy coloring produces the optimum results. Is ...

1
2 3 4 5
8