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