Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [greedy-algorithms]

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

0
votes
1answer
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$ ...
0
votes
1answer
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 ...
6
votes
1answer
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 ...
0
votes
1answer
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 ...
6
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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 {...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
3answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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
1
vote
1answer
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$....
2
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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. ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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$, ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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) ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
4
votes
1answer
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 ...
3
votes
2answers
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$, ...
0
votes
1answer
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, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
25
votes
2answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
2answers
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: ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
2answers
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, ...
-1
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
86 views

Information about ε-greedy algorithms

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 ...
7
votes
1answer
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 ...
1
vote
0answers
92 views

Minimum feedback vertex set [closed]

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 ...
0
votes
0answers
46 views

Approximate algorithm to find the minimum score

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$, ...