# Questions tagged [greedy-algorithms]

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

342 questions
Filter by
Sorted by
Tagged with
240 views

### what is the significance of the word “Sub-problems” in Greedy Method?

With respect to Dynamic Programming we make a statement that : Greedy algorithm have a local choice of the sub-problems whereas Dynamic programming would solve the all sub-problems and then ...
106 views

### Why does the given solution to this problem works? How can it's correctness be proven?

This is a question asked in Adobe interview: Given heights of n towers and a value k. We need to either increase or decrease height of every tower by k (only once) where k > 0. The task is to ...
55 views

36 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 ...
99 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 ...
47 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 ...
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 ...
619 views

### set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
431 views

### Greedy Algorithm Proof Min Swaps

Problem to get the min. no. of swaps required for arranging pairs togethe. There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with ...
37 views

### directed edges in an undirected graph [duplicate]

Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even. For example, consider a graph ...
684 views

### Minimum Number of Integers From a List that Add up to N (Dynamic Programming)

A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically: Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where ...
63 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?
103 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 ...