Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
344 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
2
votes
1answer
840 views

GSAT incompleteness example

The GSAT (Greedy Satisfiability) algorithm can be used to find a solution to a search problem encoded in CNF. I'm aware that since GSAT is greedy, it is incomplete (which means there would be cases ...
2
votes
1answer
582 views

Finding an instance of an n-element set cover

Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter ...
2
votes
1answer
1k views

Solving a variant of interval scheduling problem [duplicate]

I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have a ...
2
votes
2answers
1k views

“Flow layouts” inside a GUI — how do I come up with a good algorithm?

I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode): ...
2
votes
1answer
12 views

Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment. Say that ...
2
votes
2answers
87 views

Maximize number of subsets

Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words, $...
2
votes
1answer
55 views

2-Approximation algorithm for for messages across a cyclic network

Question There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
2
votes
1answer
648 views

How to understand the solution to Task Scheduler problem on LeetCode?

LeetCode Task Scheduler problem is the following: Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any ...
2
votes
1answer
62 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 ...
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 ...
2
votes
1answer
116 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
461 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 $...
2
votes
1answer
92 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 ...
2
votes
1answer
180 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). ...
2
votes
1answer
65 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+...
2
votes
1answer
200 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 ...
2
votes
1answer
73 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$ ...
2
votes
1answer
64 views

Identifying set of longest time periods excluding overlapping time ranages

Suppose I have set of time records as follows 08:00 - 12:00 10:00 - 12:00 08:00 - 13:00 13:00 - 19:00 12:00 - 17:00 Now I want to select set of time records that ...
2
votes
1answer
115 views

Selecting optimal order of questions to minimize total time

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ...
2
votes
2answers
4k 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 {...
2
votes
3answers
1k views

Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm

The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as ...
2
votes
1answer
637 views

Running time of greedy scheduling algorithm

Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum. Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$....
2
votes
1answer
3k views

A greedy approximation algorithm for max k-cut

The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$ so that the total cost of edges running ...
2
votes
1answer
906 views

Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
2
votes
1answer
2k views

Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some ...
2
votes
1answer
33 views

Modified topological sort

I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways. Let's define a &...
2
votes
0answers
46 views

Maximize the minimum gap while scheduling within intervals?

Problem There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals? For ...
2
votes
0answers
39 views

Choosing a method for algorithmic problems - is it an art or science?

I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
2
votes
0answers
23 views

Optimal strategy for tossing three dependent coins

Suppose that I have three correlated coins. The marginal probability of Head of coin $i$ is denoted by $p_i$. The conditional probability of head for coin $i$ given the outcomes of coin $j$ and $k$ ...
2
votes
0answers
82 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 ...
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 ...
2
votes
1answer
432 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
2
votes
1answer
239 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
0answers
259 views

Weighted Sorting Algorithm

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation. Is there any ...
2
votes
0answers
192 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
0answers
520 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 ...
2
votes
0answers
2k views

Why is it necessary to sort according to the starting time in the interval partitioning problem?

What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample ? Note- (refer here for detailed definition) ...
2
votes
0answers
161 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
2answers
1k views

minimum spanning tree and minimum heavyweight spanning tree [duplicate]

a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible. Formally, input : given connected undirected weighted graph, $G$. output : a spanning tree $T$...
2
votes
0answers
732 views

Single machine job scheduling (Greedy heuristic)

Here is a variation of a job-scheduling Problem. Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge ...
2
votes
0answers
673 views

Other greedy choices to solve activity selection problem

I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities. But surely ...
1
vote
5answers
600 views

Correctness of the greedy algorithm

I am trying to solve the following problem: Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of ...
1
vote
2answers
3k views

Vertex cover algorithms for directed graphs?

I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph. Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a ...
1
vote
1answer
275 views

Can sampling remove the limitations in greedy algorithm?

Given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or some structured manner reduce or remove the limitations of ...
1
vote
2answers
667 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 ...
1
vote
1answer
88 views

Information about ε-greedy algorithms

I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms ...
1
vote
2answers
360 views

Find the coins required which sum to S

Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once). I was recently studying ...
1
vote
3answers
33 views

Greedy Algorithm: Optimal Substructure

I don't have a CS degree but I have recently taken up studying algorithms very seriously. I have been studying greedy and dynamic programming for days and I come across the below definition a lot, ...
1
vote
2answers
69 views

Best approach to resource allocation problem

Problem The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...

1 2
3
4 5
7