Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
5
votes
0answers
124 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 ...
2
votes
1answer
31 views

Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is ...
0
votes
0answers
13 views

How to detect self loop in graph using greedy algorithm if given list of number of degrees

if you are given list of n integers that represents the degree of a graph. How to detect if there self loop in the graph using greedy algorithm.
0
votes
3answers
45 views

Optimality of a Greedy Algorithm

If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you ...
1
vote
1answer
37 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
26 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
1answer
185 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
1
vote
2answers
165 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 ...
0
votes
1answer
251 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 ...
1
vote
1answer
141 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$)...
4
votes
1answer
243 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 ...
0
votes
2answers
46 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
66 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 ...
2
votes
1answer
31 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 ...
7
votes
1answer
299 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
57 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
36 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
44 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
0answers
23 views

Activity Selection with changable start time

I have been studying a problem in my work and I have reduced my problem to likewise Activity Selection problem. It is a problem that I know and I am familiar with the greedy solution. However, in my ...
0
votes
1answer
44 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 ...
1
vote
3answers
777 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.
0
votes
0answers
57 views

How does ordering paradigm differs from subset paradigm in greedy method?

What is the difference between subset paradigm and ordering paradigm of greedy method approaches? More precisely I didn't understood how does the ordering paradigm differs from subset paradigm? ...
3
votes
1answer
75 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, ...
2
votes
1answer
67 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
50 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 ...
1
vote
1answer
20 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, ...
0
votes
0answers
37 views

Improving on Monte-Carlo

Can I improve on a Monte-Carlo search for the problem, described? So I have a graph/network consisting of segments a1, a2, ..., b1, b2, ..., and c1, c2, ... For all the underlying segments there is ...
2
votes
0answers
52 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
80 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
1answer
68 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 ...
4
votes
1answer
468 views

2 approximation algorithm for the single machine scheduling problem

We are given one machine and $n$ jobs that we want to process. For the $n$ jobs we have the following data: $r_{1}, ... , r_{n}$ are the release times $p_{1}, ... , p_{n}$ are the processing times ...
1
vote
2answers
351 views

Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
0
votes
0answers
29 views

Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
2
votes
0answers
128 views

Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
2
votes
1answer
47 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, the $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+...
0
votes
0answers
21 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
58 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 ...
3
votes
1answer
811 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
1answer
51 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
50 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
95 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
113 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 ...
2
votes
3answers
427 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 ...
1
vote
0answers
33 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
2answers
984 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
47 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
357 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
3k 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 ...
3
votes
2answers
65 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 ...