Questions tagged [greedy-algorithms]

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

369 questions
Filter by
Sorted by
Tagged with
79 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 ...
1k 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 ...
735 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 ...
77 views

65 views

272 views

Verifying if a greedy solution is optimal for a specific instance (Set cover)

Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution. Is there an efficient way of verifying if, for that particular instance, the given solution ...
863 views

Troubles understanding this Interval Scheduling question

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question. Consider the ...
2k views

Greedy algorithms: Minimum sum number pairing

Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair. I think the optimal pairing is obtained by sorting the original set, pairing the first element ...
100 views

Generating a Covering Array Matrix with Simulated Annealing

I've been reading the following paper to understand how I can develop a non deterministic algorithm for test cases generation https://www.researchgate.net/publication/293043297_A_two-...
273 views

A general algorithm for greedy algorithms

I have been refreshing on greedy algorithms as an algorithm design technique. I have read many sources for an explanation of what a greedy algorithm is, because I would like to put together a general ...
67 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 ...
1k views

What algorithm does OLA and UBER use for allotting taxis

More specifically : lets say i have 5 taxis , each available for booking at t=0; i have two days (48 hrs) with me how can I maximise their booking . I may not be able to clarify the question , this ...
112 views

302 views

Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Definitions: An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
765 views

Vertex Cover special cases

This was from a test from my university: Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum ...
159 views

When does greediness guarantee optimality?

I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution. Here is a motivating example. Suppose you are trying ...
5k views

Is there a greedy algorithm to solve the assignment problem?

The assignment problem is defined as: There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known ...
I'm taking a course about submodular functions and their applications towards influence maximization in a network. We've been discussing a greedy algorithm for selecting $k$ initial nodes to maximize ...