Stack Exchange Network

Stack Exchange network consists of 174 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 about algorithms that make at each step the locally optimal choice.

2
votes
0answers
100 views

Proof of a greedy algorithm concerning “Buy and Resell Problem” [on hold]

"Buy and Resell Problem" is a classical optimization problem. It can be described in the following way: There are $n$ cities. For each city, the price of products in this city is given (a positive ...
0
votes
1answer
64 views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
2
votes
0answers
34 views

Maximum number of non-overlapping rectangles where each contains a minimum number of points

Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
2
votes
1answer
48 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 ...
1
vote
1answer
27 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, ...
1
vote
1answer
40 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) ...
1
vote
1answer
33 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 ...
1
vote
1answer
28 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 ...
0
votes
1answer
31 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 ...
2
votes
1answer
30 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). ...
1
vote
1answer
60 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 ...
2
votes
2answers
54 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 ...
0
votes
1answer
29 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 ...
0
votes
1answer
46 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 ...
0
votes
1answer
59 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 ...
0
votes
0answers
31 views

How to approach solving this variation of the Job Scheduling Problem?

Question: Given N processes with Arrival times and Processing times, calculate and print minimum number of CPUs required if maximum allowed Turnaround time for each process is 10 units. Turnaround ...
0
votes
1answer
18 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 ...
0
votes
1answer
51 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 ...
0
votes
0answers
33 views

Gas Station Problem Variation

My friend challenged me with this question. I've enjoyed two weeks with ocassional problem-solving sessions but it became such bug in my head that I needed to sign up :) We have: car with fuel ...
0
votes
0answers
28 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 ...
1
vote
0answers
48 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?
2
votes
1answer
33 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 ...
1
vote
1answer
61 views

Insertion Heuristics to the TSP Problem

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 ...
0
votes
2answers
63 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 ...
3
votes
1answer
132 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....
1
vote
1answer
35 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$ ...
1
vote
2answers
58 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: ...
1
vote
0answers
74 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 ...
1
vote
1answer
67 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 ...
0
votes
0answers
49 views

Two Pointer Algorithm Proof (Greedy) Roadblock

I am practicing some competitive programming problems and encountered a version of the two pointer algorithm that I got stuck trying to prove its correctness. Here is the outline. Input : An array of ...
2
votes
1answer
80 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 ...
0
votes
0answers
19 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. ...
0
votes
1answer
131 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 ...
0
votes
0answers
57 views

Time Management Scheduling Problem

I am interested in solving a problem related to time management. Suppose you are given $N$ intervals, where the $i$th interval has start time $s_i$ and end time $e_i$, as well as amount $a_i$. Each ...
1
vote
1answer
52 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, ...
0
votes
2answers
128 views

greedy algorithms - minimizing total payment

The question: I want to buy $n$ books. In the book store there's a big sale according to which, if you buy three books, then the cheapest book in any triplet costs only 20% of its full price. Let $...
1
vote
1answer
18 views

Group values up to a threshold and minimize groups

Given a threshold $t$ and a list of numbers $N$. $\forall n \in N: n \leq t$ Now group the numbers so that the sum of the numbers $s$ is lower or equal $t$. Minimize the amount of groups. Example: $...
0
votes
2answers
137 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.
1
vote
2answers
39 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 ...
6
votes
0answers
149 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')$ ...
1
vote
0answers
32 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 ...
1
vote
0answers
187 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 ...
1
vote
0answers
46 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. ...
0
votes
0answers
84 views

Greedy algorithmn scheduling given a single machine and multiple jobs with deadlines

There is a single processor and a bunch of jobs are scheduled. Each job has a processing time and a deadline to finish and deadline > processing time. Jobs will not exceed said deadline and may ...
1
vote
1answer
98 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 ...
0
votes
0answers
61 views

Finding the minimum number of subsets of intervals such that they don't overlap with each other in their subset - Correctness

The problem is as follows : Given a set of $ n $ intervals having the form $ [s_{i},f_{i} ] $ find a partition of this interval having the minimum amount of elements, such that there is no element ...
2
votes
2answers
58 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 ...
1
vote
1answer
226 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 ...
0
votes
0answers
253 views

Proving a greedy algorithm

Hey so I'm studying for a midterm and I've run into this problem in the material. I'm not sure how to go about solving it. If I use regular induction in part a, I get something a bit tautological. Any ...
1
vote
0answers
111 views

With restrictions, can the knapsack puzzle be solved with a greedy algorithm?

I know that with the knapsack problem in general, there is no known greedy algorithm to solve it. But, say we add the following constraints: • All items have values equal to their weights (for all $...