Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
455 questions
1
vote
1
answer
108
views
Prove optimality of a sorting algorithm
I'm working on proving a greedy solution to the problem in Codeforces 205B, which states:
Given an array of integers a of length ...
3
votes
2
answers
240
views
Show that in every pure SPNE, the first agent weakly prefers their own bundle to any other
Suppose we have a set $N$ of $n$ players and a set $M$ of $m$ items. We are given a matrix $P_{n \times m}$ whose element $p_{ij} \geq 0$ $(i \in N, m \in M)$ denotes the valuation of good $j$ by ...
- 108
0
votes
0
answers
76
views
Graham's Greedy Algorithm is optimal for (2m) machines
I am reading up on Graham's algorithm and want to prove it's $4/3 - 1/(3m)$ optimality.
To do that, we need to prove that if $j$ is the last job assigned to the most heavily loaded machine in the ...
- 71
2
votes
1
answer
272
views
Assignment problem, but minimise the greatest individual cost, rather than the aggregate cost
https://en.wikipedia.org/wiki/Hungarian_algorithm
In the assignment problem as described above, the goal is to find an assignment that minimizes the total cost, and the Hungarian Algoirthm is a ...
- 121
0
votes
0
answers
36
views
Modified interval scheduling (greedy algorithm)
I have a question related to the interval scheduling problem (greedy algorithm). When solving a typical interval scheduling problem using a greedy algorithm, we select intervals based on the earliest ...
0
votes
0
answers
45
views
Algorithm for Bin Packing with fixed N Bins, with goal of spreading as evenly as possible (minimizing deviation from average)
Essentially I have N bins of equal size in which I want to spread M objects of arbitrary-ish size as evenly as possible.
Arbitrary-ish-size in that the largest object is much much smaller than any ...
- 101
2
votes
1
answer
113
views
Approximation algorithm for a problem similar to load balancing
This's exercise $7$ of chp $11$ from the popular book algorithm design by Jon and Eva. It's about designing a $2$-approximation algorithm for a problem similar to Load balancing on parallel machine. ...
- 225
1
vote
1
answer
131
views
Showing Dijkstra's algorithm works for bridge negative edges
Let $G=(V,E)$ a directed graph with weight function $w:E \to R$. let $s \in V$ a vertex s.t it has path to any other vertex in $G$. Suppose that every negative vertex in this graph is bridge edge, ...
- 181
0
votes
0
answers
75
views
Feedback vertex set algorithm problem
Problem Context
I am working on solving the Minimum Feedback Vertex Set (MinFVS) problem on a 2D geometric graph. A geometric graph consists of vertices defined as points in a 2D plane, with edges ...
- 1
0
votes
0
answers
51
views
Input Example for Load Balancing: Greedy vs Ordered Scheduling Algorithm
I'm working on a problem involving load balancing across three machines. I need to find an input example (a list of job sizes) where the greedy scheduling algorithm produces a strictly lower makespan ...
1
vote
1
answer
156
views
Greedy algoithm exchange proof for array symmetry swap to reduce same neighbour elements
Given an array of integers of size n, the task is to reduce the disturbance of the array where disturbance is counted as number of same neighbouring pairs.
Ex:
2 1 2 2 1 1
The disturbance is 2. As ...
- 11
2
votes
1
answer
567
views
Split a String Into the Max Number of Unique Substrings: O(n^2) solution explanation (Leetcode 1593)
I found an $O(n^2)$ accepted submission to LeetCode 1593, and I don't understand why it works.
I have included the problem statement, my understanding of what the $O(n^2)$ code does, the submitted ...
- 173
0
votes
2
answers
224
views
Simple yet un-solvable algorithm
I have tried writing an algorithm which will solve the problem:
"Consider the set $X:= \{0,...,14\}$. Define the 'blocks' of $X$ to be the 4-element subsets of $X$. For each block, let all the ...
- 1
0
votes
1
answer
146
views
Smallest sum not obtainable using a subset of elements in array greater than the minimum element
I am solving a variation of the missing coin sum problem, modified to be as follows:
You have n coins with positive integer values. What is the smallest
sum greater than the minimum coin in the array ...
- 133
2
votes
0
answers
52
views
Algorithm for maximizing the number of pairs removed from a sorted sequence under a dubling condition
Given a non-decreasing sequence of $n$ positive integers $a_1 \leq a_2 \leq \dots \leq a_n$, we are allowed to modify this sequence by performing the following operation: we select two elements $a_i, ...
- 21