Questions tagged [greedy-algorithms]

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

226 questions
63 views

Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks

Lets just say I have two lists of the running time of tasks A and B. Formally, I would have: A = {a_1, a_2, a_3 ... a_n} B = {b_1, b_2, b_3 ... b_n} I can only ...
33 views

Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?

I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, ...
54 views

Candy Problem for k size window

I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) ...
76 views

Mimimum spanning tree with a constraint on number of certain types of edges

I have the the following problem. Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
75 views

what is the significance of the word “Sub-problems” in Greedy Method?

With respect to Dynamic Programming we make a statement that : Greedy algorithm have a local choice of the sub-problems whereas Dynamic programming would solve the all sub-problems and then ...
291 views

Can Tug of war problem be solved by DP or greedy approach?

For problem explanation: https://www.geeksforgeeks.org/tug-of-war/ I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ...
83 views

How to restore diagonal-symmetric matrix that has been shuffled?

I have a square matrix M, which originally looked like this: 133 199 101 121 142 133 199 101 156 142 133 199 108 156 142 133 (so symmetric around the diagonal). ...
127 views

Why this greedy algorithm does not return the optimal solution to this NP-hard problem?

Problem: In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective ...
71 views

Shortest travelling cost if we have bunch of points in 2D plane

I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
40 views

Minimum square side length to enclose n circles of radius r

I thought of a problem but have no idea how to solve it. The problem is as follows: Given 2 numbers, n and r, find the side length (S) of the smallest square that encloses n circles each of radius r ...
487 views

proof of correctness for greedy knapsack algorithm

I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement ...
232 views

Does an algorithm exist for scheduling jobs on two processors?

I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found ...
35 views

Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit

I have such a task at university: we have n tasks, i-th of them can be done between moment b(i) and e(i). If we decide to perform a task in moment x, we finish performing it in moment x+1. We can ...
23 views

Interval Scheduling Confusion

I am reading some notes about interval scheduling. I gives the following diagram: and states that: r2 is compatible with r3, while r2 and r1 are conflicting. Similarly, the set {r1, r3, r4} is ...
81 views

Efficient traffic allocation

Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the ...
36 views

Algorithm to check if exists a valid streaming sequence in O(n)?

Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
55 views

Is there any greedy solution for bitonic tour

I have found dynamic solution for Bitonic tour but I could not find any greedy approach for this problem. Is it possible to solve it in a greedy manner?
101 views

Activity Selection and Matroid Theory

Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property. I was trying to understand this. So far, I was ...
2k views

How does the nearest insertion heuristic for TSP work?

In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson ...
87 views

Greedy Heuristic for the Traveling Salesperson Problem

We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any ...
497 views

Find the minimum set of intervals for given set of numbers

For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$ the answer is {\{[1....
57 views

What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima. To avoid this problem, we may keep track of the best $n > 1$ ...
63 views

Online set filling with redistributions

Edited: Suppose we have 4 sets $A, B, C, D$ which can can hold a maximum of two elements, each. Now, elements ($E_i$) arrive serially with properties such as: ...
84 views

Algorythm for creating Number-Rows

Given is a list of numbers. Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is ...
71 views

Why does the given solution to this problem works? How can it's correctness be proven?

This is a question asked in Adobe interview: Given heights of n towers and a value k. We need to either increase or decrease height of every tower by k (only once) where k > 0. The task is to ...
121 views

Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?

The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So ...
34 views

Table of incompatible turns in an intersection (steps to writing a program)

I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads. ...
315 views

Will a Greedy algorithm give a correct result for minimum partition?

Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem? Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now ...
83 views

Can LP for matroid polytopes be solved using the greedy algorithm?

For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, ...
259 views

553 views

Stable matching problem is greedy or Dynamic?

Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.
55 views

Element wise product sum of two arrays

I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving ...
225 views

The heaviest induced subgraph problem

I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
42 views

minimal packing analysis using greedy

First, for the sake of notation, suppose a finite set A, where A is a set of real numbers. Then the function f(A) is defined as the sum of all the elements in A. Then here's the following problem. I ...
406 views

Solving a Rod Cutting Problem

I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price. I ...
77 views

how to prove correctness of this greedy algorithm? [duplicate]

I did exercise problem from Pittsburgh university cs department. homework. Question 8 is somewhat exciting. Q8 is solved using greedy algorithm but I have no idea how to prove. Below is Question. ...
117 views

Greedy algorithm: Minimizing the maximum of a list

Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last ...
66 views

Optimal Partition of Book Chapters

Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions: by the end of each day, you ...
545 views

Optimizing greedy solution for choice game

Consider the following game: Two players choose numbers from a sequence of integers with even number of elements. The two can only choose from either the front or the end of the sequence. The purpose ...