Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
6
votes
0answers
213 views

Correctness of a greedy Algorithm on Knockout Tournaments

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
1
vote
1answer
343 views

Maximum number of similar groups of a given size that can be made from a given array

I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$. I need to find the maximum number of groups with the ...
0
votes
0answers
274 views

Job Scheduling with deadline with $nlogn$ algorithm

We know that there is a Greedy algorithm for scheduling of $n$ jobs which each job has its own deadline and profit. In greedy algorithm, we sort the set by their profit descendant, And if a job can ...
2
votes
2answers
2k views

Why this greedy algorithm fails in rod cutting problem?

Recall the rod cutting problem. Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and ...
2
votes
2answers
748 views

Knapsack with a fixed number of weights

Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There ...
1
vote
1answer
1k views

Selecting elements from two arrays to get a target sum

Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer. Design an algorithm to solve the following problem. For each index $i$ ($1\leq i \leq n$)...
2
votes
1answer
63 views

Determine aproximation factor in a greedy algorithm

Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences. We want to choose a menu such that we minimize the cost and ...
1
vote
0answers
101 views

Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem

The unweighted maximum coverage problem is defined as follows: Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$. Objective: find a subset $S' \subseteq S$ such ...
1
vote
0answers
48 views

Weighted Activity Selection Problem with allowing shifting starting time

I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists. In my case, I am allowed to ...
-1
votes
1answer
396 views

You have K amoebas and one amoeba can divide into A,B,C amoebas after one instruction then find the minimum no. of instruction to have N amoebas

. You have developed an artificial amoeba, and you can control exactly how it divides. Each individual amoeba can be instructed to divide into A, B, or C amoebas. That is, if you instruct an amoeba to ...
0
votes
1answer
50 views

Schedule each entree so that all entrees are completed in the shortest amount of time

Lets say we have plenty people to dress up entrees, but only one chef to cook them. Each entree $E_i$, takes $c_i$ time to cook and $d_i$ time to "dress up". The dressing up of entrees can occur while ...
3
votes
1answer
595 views

Hitting Set Problem with non-minimal Greedy Algorithm

The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
1
vote
1answer
199 views

Converting a greedy algorithm to a dynamic programming algorithm

Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be: First, find a maximum indpendent set of ...
3
votes
1answer
98 views

Optimal solution for Weighted points problem

Problem: Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, ...
1
vote
1answer
38 views

Trivial solution to the Continuous Knapsack problem

I am a bit puzzled as to why the continuous knapsack problem is a non-trivial problem https://en.m.wikipedia.org/wiki/Continuous_knapsack_problem Using the terminology in the Wikipedia link above, ...
2
votes
0answers
83 views

Interval partitioning problem different approach - arrange lectures in minimum number of classrooms

The problem of scheduling lectures in minimum number of classrooms is as follows: Find minimum number of classrooms to schedule all lecture so that no two occur at the same time in the same room. The ...
3
votes
1answer
194 views

Greedy Heuristics with an Altered Subset Sum/Partition Problem

Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, ...
0
votes
0answers
22 views

Design a greedy algorithm by intermingling two sequences [duplicate]

I find myself solving problems for a test and the next problem I still can't solve it. There are n ordered sequences, $S_1$ to $S_n$. It is requested to intermingling them to obtain a single sequence,...
1
vote
1answer
99 views

Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

The problem is in this other question. Why does this always work? It's not clear to me how one would use induction. For $n = 3$, a quick calculation shows it works, however, I don't think it ...
2
votes
1answer
53 views

How do I minimize the cost of some algorithm that performs some operation on a list?

I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem ...
0
votes
2answers
146 views

largest subset of pairwise intersecting intervals [closed]

Given a set of intervals on the real line, compute the largest subset of pairwise intersecting intervals (an interval in the subset must intersect with every other interval in the subset). Design a ...
2
votes
1answer
500 views

Gas Station problem : Fixed path variation

Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path ...
3
votes
1answer
302 views

Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one. A greedy algorithm for this would keep removing digits ...
1
vote
0answers
34 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
3answers
827 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 ...
3
votes
2answers
2k 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
140 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 ...
3
votes
2answers
77 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 ...
2
votes
1answer
119 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 ...
0
votes
0answers
57 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 ...
2
votes
0answers
50 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
151 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
442 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
0
votes
0answers
153 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 ...
0
votes
2answers
888 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
1answer
183 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 ...
2
votes
1answer
246 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 <...
1
vote
2answers
103 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
464 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 $...
1
vote
1answer
254 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
551 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 ...
1
vote
1answer
65 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
236 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 ...
3
votes
2answers
581 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
54 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
2k 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
83 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 ...
2
votes
1answer
249 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
44 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 of ...
2
votes
4answers
2k 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 ...

1 2
3
4 5
7