# Questions tagged [greedy-algorithms]

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

65 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
154 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 ...
151 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 ...
266 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 ...
94 views

### How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
230 views

### Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
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$ ...
67 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 ...
41 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 ...
298 views

Different machine has different efficiency on different tasks, like: ...
181 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 ...
162 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 ...
498 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 ...
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) ...
717 views

30 views

### What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?

Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem). A trivial ...
77 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 ...
40 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 ...
221 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 ...
59 views

### Is there any greedy solution for bitonic tour

I have found dynamic solution for Bitonic tour but I could not find any greedy approach for this problem. Is it possible to solve it in a greedy manner?
99 views

### Algorythm for creating Number-Rows

Given is a list of numbers. Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is ...
49 views

### minimal packing analysis using greedy

First, for the sake of notation, suppose a finite set A, where A is a set of real numbers. Then the function f(A) is defined as the sum of all the elements in A. Then here's the following problem. I ...
357 views

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 ...
163 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? ...
38 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 ...