Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
342
questions
1
vote
0answers
11 views
How to find optimal greedy algorithm?
This is an intriguing question 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 attend work online ...
0
votes
0answers
6 views
Minimum Number of Refueling Stops with DP
This is a question from Leetcode and i wanted to solve with Dynamic Programming. upon seeing the solution, i am not able to get the intution behind the logic. I was able to understand the solution ...
1
vote
0answers
17 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 ...
1
vote
1answer
70 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
1answer
60 views
What Makes an Algorthim Greedy [Graph Coloring Algorithm]
I have a simple graph G = (V,E) and each vertex has a range [a,b].Every two vertices are connected only if [a_1,b_1] and [a_2,b_2] have a common subrange.
Each range of vertex is rV1 = [0,5] rV2 = [1,...
0
votes
0answers
35 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
33 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
21 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
25 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,...
1
vote
0answers
27 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 ...
36
votes
3answers
36k views
How to prove greedy algorithm is correct
I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
-1
votes
1answer
67 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
25 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
24 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 ...
2
votes
1answer
429 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
1
vote
2answers
360 views
FInding the combination with the least number of elements from and array of integers, given an integer sum
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
1answer
412 views
Proof that the length of the largest ascending subsequence is the number of decreasing subsequences
Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is ...
0
votes
0answers
40 views
maximum sum of diameter of tree + leaf removal
Problem: A tree of n nodes is given. Have a sum variable. Choose the leaves furthest from one and other and add their distance(the number of edges between them) to the sum variable. Now remove one of ...
1
vote
1answer
33 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
44 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:...
4
votes
1answer
324 views
An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number
Suppose there is an unlimited number of pipes, each has length $x$ meters.
There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given.
For example ...
2
votes
1answer
43 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
25 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 ...
1
vote
1answer
73 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
31 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 ...
0
votes
1answer
32 views
A problem about Huffman codeword
Under Huffman Encoding, what circumstances codeword length of each character
be equal?(suppose number of character is power of 2)
I think if all frequency of characters is same then codeword length ...
1
vote
1answer
60 views
Greedy algorithm for maintaining drugs
Given $n$ drugs such that each drug $d_i$ should maintain in interval
$[c_i,h_i]$.We want to minimize number of containers to maintain
medicines in compatible interval.
My answer is as follows:
I use ...
2
votes
1answer
12 views
Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times
I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment.
Say that ...
4
votes
1answer
113 views
Hamiltonian path greedy and anti-greedy algorithms
I had this question on a problem set recently, but I wasn't sure how to solve it.
Given a complete weighted undirected graph $G$, here are two "algorithms" to find a Hamiltonian path:
...
0
votes
0answers
89 views
Finding name of a specific problem
Input : $x \in \mathbb Z$ and $a_1,a_2,\dots,a_n \in \mathbb N$.
Output : $b_1,b_2,\dots,b_n \in \mathbb Z$ such that $\sum_{i} a_i b_i=x$ and $\sum_{i}|b_i|$ is minimized.
Main question is, can we ...
0
votes
0answers
54 views
Need help with a very specific Greedy Algorithm. Are there fast solutions?
i need help for a specific problem i have at work.
You have N number of rows in an array, each with some distribution of Numbers that range from 0 to N.Given an array of size 1000:
Row 1 might look ...
0
votes
0answers
29 views
Minimum cost bin assignment
I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but ...
1
vote
1answer
32 views
Must an optimization problem with a greedy algorithm belong to P?
If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
1
vote
2answers
69 views
Best approach to resource allocation problem
Problem
The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...
0
votes
1answer
25 views
Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups [duplicate]
Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time ...
2
votes
2answers
87 views
Maximize number of subsets
Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words,
$...
4
votes
1answer
48 views
Is the following Greedy algorithm to generate Gray Codes always correct?
I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites)....
2
votes
1answer
344 views
Going deeper with pseudo-polynomial time algorithm for set partitioning
If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next?
To illustrate this ...
0
votes
1answer
42 views
How to (Efficiently) Sort a List of Items with Parent/Child Relationship
I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member ...
1
vote
1answer
45 views
Maximum Independent Set of special Directed Graph
I was given this special type of Directed Graph and was asked to find it's Maximum Independent Set.
Graph Properties :
Graph has $N$ vertices and $N$ edges
There can be no edge from a vertex $v$ to ...
3
votes
1answer
114 views
Greedy algorithm for subset sum on powers of 2
I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after ...
0
votes
0answers
23 views
Rearrange string k distance Apart
The question statement is as follows:
Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. All input strings are ...
1
vote
0answers
19 views
Greedy Best-First Search Performance for Tree and Graph Space
I am currently reviewing the GBFS algorithm and when looking at its completeness I am confused between the difference of it being
not optimal in Tree Search for Finite and Infinite Spaces
that it is ...
0
votes
2answers
52 views
Highest Product of X Items
🧩 How do you find the highest product of X items?
This should optimize for runtime complexity and protect from overflows from large products.
Inputs
An array of both positive and negative Ints ...
3
votes
0answers
18 views
Spanning hypertree which connects the vertices as slowly as possible
I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
2
votes
1answer
54 views
2-Approximation algorithm for for messages across a cyclic network
Question
There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
1
vote
0answers
32 views
Does the existence of a matroid structure imply that the greedy algorithm is optimal?
I was going through the topic of matroid structures for the problems like Activity selection ,minimum spanning tree. I also came to know how to solve if a problem exhibits matroid structure. The ...
2
votes
1answer
33 views
Modified topological sort
I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways.
Let's define a &...
0
votes
0answers
29 views
Greedy Proof: For coin denomination systems, faster proof to ensure greedy solution yields the optimal solution
I have reasons to believe that there is a faster way to confirm, that for coin denomination systems if the greedy solution yields the optimal solution or not.
I believe that if you check that for all ...
2
votes
1answer
619 views
How to understand the solution to Task Scheduler problem on LeetCode?
LeetCode Task Scheduler problem is the following:
Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any ...
