Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
317
questions
1
vote
2answers
41 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
20 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 ...
1
vote
1answer
49 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,...
3
votes
1answer
37 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
2answers
79 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,
$...
0
votes
1answer
20 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
38 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
62 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
16 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
16 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 ...
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, ...
0
votes
2answers
45 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 ...
-2
votes
1answer
59 views
Greedy algorithm for problem asking for solution of size *at most* $k$
Given an integer $k$ and a complete weighted bipartite graph with sides $A,B$ in which the weight of the edge $(i,j)$ is $c_{ij} \geq 0$, we want to find a set $S$ of at most $k$ edges that maximizes $...
2
votes
1answer
38 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$) ...
2
votes
1answer
31 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 &...
1
vote
0answers
29 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 ...
0
votes
0answers
25 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 ...
1
vote
1answer
105 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 ...
1
vote
1answer
43 views
Serving $k$ customers with bounded time window
A person provides a service and he/she can serve $k$ clients each minute.
Now, client number $i$ comes at the beginning of minute $a_{i}$ and waits $w_{i}$ minutes to receive the service and if they ...
0
votes
1answer
41 views
Ordering the tasks to minimize penalties
So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows:
In your calendar you have an $L$ list of all the tasks you need to complete today. ...
-2
votes
1answer
84 views
Correctness proof of a greedy approximation algorithm
How do I prove the correctness of this algorithm?
2
votes
0answers
28 views
Maximize the minimum gap while scheduling within intervals?
Problem
There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals?
For ...
0
votes
2answers
59 views
Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?
There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:
There are n tasks, each task ...
0
votes
1answer
34 views
Mathematical expression for the quantity that we are maximising in the stock buying and selling problem
Problem Statement:
Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.
Design an algorithm to find the maximum profit. You may complete as many ...
0
votes
2answers
59 views
What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]
I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, ...
-1
votes
1answer
34 views
Prove following statement about Kruskal Algorithm
Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)āE that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
0
votes
0answers
49 views
Find the maximum number of valid cartesian coordinates
Given a list X containing m number of x coordinates and a list Y containing m number of y coordinates. The coordinate (x, y) is valid if and only if the difference between x and y is less than or ...
2
votes
0answers
39 views
Choosing a method for algorithmic problems - is it an art or science?
I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
0
votes
0answers
18 views
Minimizing the length a Boolean Algebra Expression in disjunctive normal form
I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
0
votes
1answer
81 views
Binary string satisfying several constraints
I'm trying to solve this problem, but without success.
Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...
1
vote
0answers
45 views
Algorithm for summation with lowest maximum temporary sum
I've got this problem on my last exam, which I struggle to deal with.
Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
4
votes
2answers
226 views
Difficulty in understanding the proof of the lemma : “Matroids exhibit the optimal-substructure property”
I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma ...
0
votes
1answer
400 views
Greedy sequential/parallel task scheduling
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 ...
0
votes
1answer
21 views
An independent d-division
I would love to have a direction for the following exercise (the material for this exercise is greedy algorithms):
Let $G = (V,E)$ an undirected graph whose vertices $V = \{v_1,\dots,v_n\}$ appear in ...
0
votes
1answer
70 views
Negative cycle detection using Bellman-Ford and its correctness
I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.
I have 2 doubts about the correctness of the algorithm:
Why are we ...
3
votes
1answer
123 views
Using a greedy algorithm to find a cut S which at least half of the edges cut
Let $G$ be an undirected graph.
Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.
I tried to think about something like choosing the vertex with the highest degree, ...
0
votes
0answers
35 views
Scheduling algorithm for overlapping jobs - single resource?
I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are ...
0
votes
1answer
57 views
Three City Scheduling
I came across the following interview question
There are 2N people a company is planning to interview. The cost of
flying the i-th person to city A is costs[i][0], and the cost of
flying the i-...
1
vote
0answers
28 views
Remove vertices to get k-connected components
In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?
0
votes
0answers
20 views
Set Cover: Understanding the algorithm with an example
I am trying to follow the following link:
Solution for an example
They have provided solution for an example using the greedy algorithm. I have got following questions:
(1)Why start with Z, cost is 7, ...
0
votes
0answers
32 views
Does this problem have a formal name?
I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. ...
1
vote
1answer
50 views
Problem related to set partitioning
Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$
Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one ...
0
votes
1answer
142 views
Minimum steps to sort array [closed]
Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values ...
2
votes
1answer
77 views
Proof of a greedy algorithm used for a variation of bin-packing problem
We are given an array of weights $W$ (all weights are positive integers), and we need to put the
weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The ...
1
vote
1answer
16 views
How proof of Hoffman algorithm greedy property starts with optimal tree T?
In this paper Claim 1 states that x and y are smallest probability and there is optimal code tree in which this two characters are siblings at the maximum depth. In proof to that claim, author starts ...
1
vote
0answers
87 views
Greedy algorithm to divide objects into the lowest number of groups of a maximum size
I have n objects of independent size s, and need to group them so that the sum of the sizes of each group is smaller than a given maximum size, and the number of groups is the smallest possible.
I ...
2
votes
1answer
214 views
N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm
So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its ...
2
votes
1answer
60 views
Proof for an algorithm to minimize $\max(a, b, c) - \min(a, b, c), a \in A, b \in B, c\in C$, A, B, C are arrays in ascending order
Problem Statement
I came across this problem here. For given arrays $A$, $B$ and $C$ arranged in ascending order, we need to minimize the objective function $f(a, b, c) = \max(a, b, c) - \min(a, b, c)...
1
vote
0answers
47 views
Looking for an algorithm or similar mathematical problem for trading ownerships in shared property
Suppose there is $N$ property. Each property is owned by multiple person. (they have shared ownership) For example: $Person_1$ owns 22% of $Property_1$, $Person_2$ owns 35% of $Property_1$ and $...
2
votes
1answer
437 views
Gas Station Problem - Dijkstra's Algorithm variation
I am trying to find an algorithm which finds the least expensive route from one town to another.
This is the general setup.
There are a series of one-way roads from some towns to other towns. Not ...