Questions tagged [greedy-algorithms]

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

1
vote
0answers
28 views

Take k numbers from the array and xor them with x to get maximum sum [duplicate]

Given an array A of n numbers and integers k and x. We can perform the following operation any number of times (including zero times). Take exactly k numbers from the array and replace each of them ...
2
votes
1answer
44 views

Selecting items from two arrays without duplicate indices to get maximum sum

Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you ...
2
votes
2answers
94 views

Split array into contiguous subarrays of approximately same sums

My question is similar to this splitting question, but my objective function is different. Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty ...
0
votes
1answer
28 views

Difference between greedy and work conserving scheduler for DAG

For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do. However, I found two different upper bounds on the computation time of $T$. For the ...
0
votes
1answer
60 views

Given n drinks, find optimum way to spend money if for each drink the price and the expiration date is given

Let's say we are given $n$ types of drinks, integer $m$ representing the budget we have and integer $d$ representing the cost of delivery when we order some drinks. For each of the $n$ drinks we are ...
3
votes
2answers
210 views

Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?

I came across this problem in Tim Roughgarden's course on Coursera: In this problem you are given as input a graph $T=(V,E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A ...
1
vote
1answer
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 ...
2
votes
2answers
45 views

Maximize number of museums visited in a day

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day. Suppose that no time is needed in ...
0
votes
1answer
92 views

Modified Knapsack Problem

I have a problem with the following optimisation problem: In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, ...
2
votes
1answer
46 views

What is an approximation factor for the Greedy Motif Search algorithm?

What is approximation factor for the Greedy Motif Search algorithm? I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native ...
2
votes
1answer
68 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
1
vote
2answers
108 views

FInding the combination with the least number of elements from and array of integers, given an integer sum

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
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, ...
0
votes
1answer
125 views

Maximize the sum of chosen numbers

I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem. Suppose there is a game with 2 players, A and B and a ...
0
votes
0answers
37 views

Interval scheduling with shared resources between steps

I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each ...
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 ...
1
vote
1answer
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 ...
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 ...
2
votes
0answers
32 views

Heuristic for searching for solutions on an 8-puzzle variant with non-unique tiles

I'm trying to perform an A* search on a particular N-puzzle variant in which some tiles are identical. More specifically, assuming an $m \times m$ grid, there are m colors with m tiles of each. The ...
0
votes
1answer
37 views

Proof for optimal interval scheduling using a Greedy Approach

You are given a set of n jobs, where each job j is associated with a size s(how much time it takes to process the job) and a weight w(how important the job is). Suppose you have only one machine ...
7
votes
1answer
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')$ ...
0
votes
0answers
81 views

Maximum matching blossom algorithm

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just ...
2
votes
1answer
81 views

Can a greedy algorithm have more than one subproblems to solve after making greedy choice?

For example: s = <s1 s2 s3> is my problem, I make greedy choice s2 and solve s1 and <...
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 {...
1
vote
2answers
67 views

Putting as many items as possible with weight and size limit

I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice. Any item has an item weight of Iw and item size of <...
2
votes
1answer
99 views

Greedy algorithm for even item distribution

I have this problem where I need to design a greedy algorithm. The problem is as follows: A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $...
0
votes
0answers
24 views

Greedy Approach without constraint and a feasibility function

We know that the Greedy Approach in general, picks an element from a set of candidate elements that satisfies a predefined criteria (selection function) and is added to the solution if it satisfies ...
1
vote
1answer
46 views

Carpet into Box

Given a carpet of size a * b [length * breadth] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or ...
3
votes
1answer
82 views

Length of shortest codeword in Huffman encoding

Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1? I thought of 2 cases where this ...
3
votes
2answers
107 views

Merging balls interview problem

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks. You are given $n$ balls on the table and all the balls are rolling towards the ...
1
vote
1answer
34 views

Minimum Spanning Tree with one particular edge minimised(continued)

I have recently encountered a coding problem, specifically, the CCC problem S4. In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
1
vote
2answers
56 views

Minimum spanning tree such that one edge can be minimised

During a computer coding exam, I have encountered such a problem. Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
-2
votes
1answer
51 views

Number Theory Problem from Local Selection Contest EPFL | ETHZ

This was a question from the 2016 local (selection) contest in ETHZ, You have a high-precision alarm clock with three operations: 1) reset wake-up time to midnight (00:00:00.000000) 2) modify the ...
1
vote
1answer
46 views

Trying to understand the question(well spaced points ?) better

Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
0
votes
1answer
307 views

Is my proof of my greedy algorithm to find subsequence correct?

Credit to KleinBerg and Taros Book Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
2
votes
1answer
63 views

Greedy Solution for Selecting Prefix Sum

Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to ...
0
votes
0answers
34 views

findining the smallest sum of squared lengths of the intervals I_{k}

Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals $I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
1
vote
1answer
83 views

What is the optimal way to solve the following optimization problem

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$. We need to compute the function $F(L)$ using the least number of transformations/...
2
votes
4answers
257 views

A greedy algorithm for the bottle filling problem

(There’s no need to write the algorithm, I just need help with the greedy choice). Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We ...
0
votes
2answers
51 views

MST Proof (Kleinburg & Tordos)

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in ...
0
votes
1answer
244 views

How this proof of fractional knapsack works?

I don't understand a step in my book proving the fractional knapsack problem: Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by ...
1
vote
2answers
153 views

set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
1answer
65 views

Greedy Algorithm Proof Min Swaps

Problem to get the min. no. of swaps required for arranging pairs togethe. There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with ...
1
vote
0answers
31 views

directed edges in an undirected graph [duplicate]

Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even. For example, consider a graph ...
1
vote
1answer
273 views

Greedy algorithm to find Minimum Dominating Set in a tree

Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
1
vote
1answer
328 views

Proof of a greedy algorithm concerning “Buy and Resell Problem”

"Buy and Resell Problem" 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 number). Now a person will travel from ...
0
votes
1answer
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 ...
1
vote
1answer
149 views

Solving “coin exchange” for coins of power values by greedy algorithm

When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$? For ...
0
votes
1answer
192 views

interval scheduling algorithm

can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this ...