# Questions tagged [greedy-algorithms]

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

226 questions
76 views

### Maximum sum difference between two sorted array elements under one condition [closed]

We're given two arrays $A$ and $B$ with size $N$ and $M$ respectively. We want to find a set $P = \{(a_1, b_1), \dots, (a_s,b_s)\}$ such that for each $i\in\{1, \dots, s\}$, $a_i\in A$, $b_i\in B$ ...
44 views

### Algorithm for finding a matrix which satisfies certain constraints [closed]

Given a list of entries entryList, determine a 4x4 matrix of which you sum up the entries specified in entryList such that there ...
260 views

### Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Definitions: An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
380 views

### Vertex Cover special cases

This was from a test from my university: Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum ...
138 views

### When does greediness guarantee optimality?

I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution. Here is a motivating example. Suppose you are trying ...
2k views

### Is there a greedy algorithm to solve the assignment problem?

The assignment problem is defined as: There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known ...
4k views

### Difference between fractional knapsack & greedy solution

I am trying to understand what the difference is between the fractional knapsack problem using dynamic programming, and the greedy solution version. Im looking at an example of the fractional problem ...
67 views

### Why is this greedy algorithm claim true?

I'm taking a course about submodular functions and their applications towards influence maximization in a network. We've been discussing a greedy algorithm for selecting $k$ initial nodes to maximize ...
1k views

### Vertex cover algorithms for directed graphs?

I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph. Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a ...
96 views

### Selecting optimal order of questions to minimize total time

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ...
2k views

### Minimum difference between two subsets of an array of integers

The Problem Suppose we have an array A[1...n] of integers, with values ranging from 0 to K (so 0<=A[i]<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {...
412 views

### How is Dijkstra's algorithm related to breadth first search(BFS)?

I've read in Introduction to algorithms(CLRS) that Dijkstra's algorithm uses ideas similar to those of BFS? I think it really makes sense with respect to Dijkstra's algorithm with relationship to BFS ...
724 views

### How to prove a greedy algorithm that uses the longest increasing subsequence?

Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...
49 views

### How can i fill shelves with products so that I have the maximum amount of sales?

I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales ...
501 views

### Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm

The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as ...
713 views

### Does a greedy strategy exist for this instance of the Bin Packing Problem?

I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 ...
3k views

### Where we Use Dynamic Programming and Greedy Algorithm? [closed]

Can someone tell me where we use Dynamic/Greedy algorithm and how we trace from the question that it will solved by any one of the above? Thanks
575 views

### Running time of greedy scheduling algorithm

Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum. Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$....
1k views

### Find minimum number of time points that cross out all intervals

Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of ...
279 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 ...
155 views

### Cards shuffling. Greedy algorithm

We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck. My idea is to create a priority queue. ...
171 views

### Unusual elevator algorithm

An elevator with a capacity of N people in a building with E floors works in a pretty unusual way. The elevator starts at the first floor and it goes to the top floor before returning to the first ...
2k views

### How does “Greedy Stays Ahead” Prove an Optimal Greedy Algorithm?

I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem. On the second page of Cornell's Greedy Stays ...
286 views

### Interval scheduling, unclear greedy proof

I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem. The proof that I am ...
3k views

### Dynamic Programming vs Greedy - coin change problem

This is a fairly common problem: Given coins of integer denominations $v_1 < v_2< ... < v_n$, make change for an amount A using as few coins as possible. Given an input of powers of $p$, ...
171 views

### Question regarding coin change algorithm (DP and greedy)

The question goes something like this: Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy ...
811 views

### How to prove greedy algorithm for number partitioning?

the partition problem (or number partitioning1) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the ...
1k views

### Why is it necessary to sort according to the starting time in the interval partitioning problem?

What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample ? Note- (refer here for detailed definition) ...
253 views

### What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?

On Codeforces, the first problem that comes up for the tag "greedy" is "50A: Domino Piling". Here is the problem: You are given a rectangular board of M × N squares. Also you are given an unlimited ...
148 views

### Information gain vs Gini impurity, for Random Forest?

I was researching about the supervised algorithm called Random Forest, that made me begin to study about decision trees, and how to induce them from a set, in order to create several predictors. My ...
392 views

### Greedy algorithm for a variation of the $k$-center problem

This is a variation of the well-known $k$-center problem with priorities given on the vertices. Problem: Let $G = (V,E)$ be a complete graph with a distances on the edges satisfying the ...
262 views

### Finding a maximum-weight base of a a matroid, in reverse

Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm: Start with an empty set (by definition of matroid, it is independent). Add ...
722 views

### set with maximum sum consisting of mutually co-prime numbers

Definitions. Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and mutually co-prime. Then find the maximum sum the set $S$ can have. Example. Let $n=10$, ...
68 views

### Discrete optimisation in 5 variables

I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, ...
69 views

### Planning interviews

This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps). Problem is: Everyday I am receiving job offers, and I have to ...
137 views

### Greedy algorithm correctness proof (UVA 10716)

Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols (UVA ...
22k 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 ...
49 views

### How can I divide a set of strings into subsets of fixed size with maximal homogeneity?

Suppose I have a set of 1000 binary strings of fixed length. I wish to divide these 1000 strings into 10 subsets of 100 strings each, in such a way that the subsets are maximally homogeneous. I want ...
137 views

### Proof for This Greedy Strategy for Equalizing An Array

Recently the following problem was posed in a private coding competition at my workplace: An array $A$ is given that has only positive integers in it. The objective is to equalize the array in ...
293 views

### In Data Mining, what does it mean to be greedy?

I am looking at a number of algorithms in Data Mining and some are described as being greedy. My issue is that they seem to be using the term greedy in different ways, which seems contradictory. For ...
166 views

### Minimizing the overall cost over groups

I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this: ...
416 views

### Please check my Huffman tree [closed]

My professor gave an example of Huffman tree. Given inputs a 80 b 10 c 20 d 50 e 100 f 35 g 60 … then the tree will be: But when i tried to solve it at home, I ...
220 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 ...
205 views

### Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
61 views

### Optimal way to join pieces when the cost of joining two pieces is $|x-y|$

There are $N$ pieces each having size $A_i$. The cost of joining a piece of size $x$ and a piece of size $y$ is $|x-y|$. What is the most optimal way to join all the pieces? Can it be solved using the ...
2k views

### A greedy approximation algorithm for max k-cut

The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$ so that the total cost of edges running ...
86 views

I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms ...
2k views

### Greedy strategy for computing the minimum number of rays that hit all balloons

The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm". The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the ...
A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $Η$ is the current graph, until there are no more cycles left.What ...
Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...