# Questions tagged [greedy-algorithms]

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

445 questions
Filter by
Sorted by
Tagged with
1 vote
15 views

### Algorithm for maximizing the number of pairs removed from a sorted sequence under a dubling condition

Given a non-decreasing sequence of n positive integers a1 ≤ a2 ≤ ... ≤ an, we are allowed to modify this sequence by performing the following operation: we select two elements ai, aj satisfying 2ai ≤ ...
• 11
27 views

### minimum operations to make array equal to target

You are given two positive integer arrays nums and target, of the same length. In a single operation, you can select any subarray of nums and increment or decrement each element within that subarray ...
95 views

### Trying to figure if greedy algorithm is a matroid (or greedoid)

I know that if I can express a problem as a (weighted) matroid M = (E, S) or a greedoid then I can assure that there is an algorithm which will give me the optimal solution. For example for matroids ...
• 136
29 views

### Algorithm for finding the minimum factorization of a tensor product expression

I originally asked a question on the Mathematica stack exchange on a similar topic here. But it seems like my question actually extends beyond Mathematica. The issue is the following. Let $a,b,d$ be ...
• 125
18 views

### Matrix optimization to minimize pruing satifying column constraints

Suppose we are given a matrix $A = [a_{i,j}]_{n\times m}$, where all entries are non-negative. In this matrix, we are allowed to exchange two elements, $a_{i,j}$ and $a_{i,j'}$, sitting in the same $i$...
• 1,860
5 views

### Deterministic online caching algorithm competitive ratio lower bound proof

I don't understand the adversary based proof in CLRS for proving lower bound of Ω (k) on competitive ratio of any deterministic online caching algorithm given that ...
• 13
26 views

### Is this knapsack variant named / studied? "Online algorithm for farthest-from-previous index"

Problem Statement: Given: an ordered list of N items, which we can refer to by index: [0, N). Goal: Write an algorithm to ...
• 123
31 views

### Selecting an Induced Subgraph from a DAG with Specific Conditions

I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$. My objective is to select an induced ...
38 views

### Greedy solution for minimum weight where all tasks are allocated

I'm trying to solve exercise 13 from Chapter 04 of Algorithms Design (Eva Tardos) books. The problem is the following: The way I solved: was to have a greedy solution, where I always choose, for an i,...
57 views

### Intuition for Using Greedy Approach in Container with Most Water Problem

Link to leetcode problem: https://leetcode.com/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150 if we consider this solution: https://leetcode.com/problems/...
1 vote
53 views

### Prove maximum score is achieved by being greedy

I have a list of tokens T, of length n. Initially I have power p and a ...
• 284
158 views

### Can every greedy problem be solved using dynamic programming?

Can every problem with a greedy solution be solved using dynamic programming? Why or why not? I'm not completely sure how to formally reason about this, my understanding about the structure of ...
132 views

### Finding optimal sequence of attacks to minimize number of soldiers needed

The problem Trying to improve my algorithms I bumped into a problem by Pedro Pablo Gómez Martín and Marco Antonio Gómez Martín, which I can summarise like this: You are given a list of enemy bases ...
• 263
143 views

### Interval scheduling; sort by ending times

You have $n$ events on your calendar, deﬁned as intervals with a start time $s_i$ and a ﬁnish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$...
33 views

### How does additional assumptions increase approximation factor?

I am studying the greedy algorithm for maximal weighted matching in arbitrary graphs. I have proven that this algorithm has approximation factor $\frac{1}{2}$. Assume now that the weights in the graph ...
• 123
19 views

### Proving Optimal Greedy Algorithms [duplicate]

How is the best way to go about proving that a greedy algorithm is optimal, inductive vs contradiction, are there parts in the proof that are key to include. I did not feel that the lesson I was ...
1 vote
278 views

### Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
1 vote
166 views

### I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

How to learn DSA if you are already working as a software engineer and have decent knowledge about development. Only thing that makes me procratinate is going over theories behind different data ...
• 119
1 vote
281 views

### Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by ...
127 views

### Visiting all nodes of a directed graph exactly once (not dfs)

Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should ...
• 67
1 vote
201 views

### Greedy Maximum Bipartite Matching

To find the maximum matching on a bipartite graph, I propose the following greedy algorithm: At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours ...
38 views

• 141
259 views

### Proof of The Optimality Of Greedy Algorithm for The Interval Scheduling Problem

I have this proof for the optimality of the greedy algorithm for the interval scheduling problem in my algorithms class, but I'm struggling to understand it fully, especially starting from the second ...
83 views

### Why do we need Optimal Substructure when proving the correctness of greedy algorithms

According to Introduction to Algorithms, to show the correctness of a greedy algorithm, we need to show: Greedy Choice Property (i.e. there exists one optimal solution that includes the greedy choice)...
• 121
1 vote
112 views

### Comparing a greedy and a brute force algorithm for NMS

Hello I am trying to implement Non Max suppression algorithm for removing overlapping bounding boxes. I have a list of bounding detected by an object detector in the format B(x,y,w,h,s) x,y are ...
90 views

### Given m intervals and an array of integers, your task is to minimize the number of operations in which you can make the elements of the array nonposit

You are given the number $m$ and $m$ intervals of the form $a_i, b_i, v_i$, where $a_i<=b_i$ and $v_i>0$ and also a number $n$ and an array $s$ of length $n$, where $s_i>0$. In one operation ...
• 1
567 views

### Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Consider the following variation on the Interval Scheduling Problem You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each ...
1 vote
68 views

### Proving a greedy algorithm of finding MINIMAL group

I am given a group $A$ of real numbers and I have to find the minimal group $B$ such that for each $a$ in $A$ there exists at least one $b$ in $B$ such that $|a-b|\leq 1$ So what I think the algorithm ...
1 vote
60 views

### Greedy algorithms criterion/ intution

Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
• 113
1 vote
176 views

### First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2

Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total ...
110 views

### How to cover elements with minimum amount of elements

I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem. I have elements from 1 to n and I am trying to cover all of the elements using the ...
76 views

### What would be an efficient algorithm that finds the maximum number of party people?

You want to organize a party and invite as many of your N friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be ...
334 views

### Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem

The following problem statement is given: Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. ...
823 views

### Maximum Independent Set of a Tree using Greedy Algorithm

I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph? ...
• 31
82 views

### How an assignment problem is solved using greedy heuristic algorithm

Consider small instance of GAP involving 5 items and 2 resources with capacities 5 and 12 respectively. If we have cost matrix Cij and also consumption matrix bij with jobs vs resources, how can we ...
39 views

### Finding the Optimal Palette for a Set of Images

Motivation I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
37 views

### Workers with certain strength carrying boxes. (Greedy)

I just had an algorithms exam and had the following problem: Supposed there are $n$ workers and $n$ objects. Each worker has a strength, $s_i$ and each object has a weight $w_i$. Each worker needs to ...
1 vote
45 views

### prove the correctness of greedy algorithm on interger optimize

Let $n$ and $r$ be positive integers. For i = 1,2,...,n, let $f_i$ be a univariate real-valued function defined in the integer domain and let $f_i(x_i)$ be $-\infty$ for negative integer $x_i$. Any ...
• 193
1 vote
55 views

### How to generate all possible colour vectors generated by greedy colouring on a graph?

Given a graph $G$, how can we generate all possible color vectors that could be generated via greedy coloring? N.B. Greedy coloring takes a graph and an order of vertices. It traverses vertices ...
877 views

### Select a subset of k intervals which form maximum length if we take union of these k intervals

Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals. Note that there are 2 cases ...
• 123
890 views

### Prove optimality of greedy strategy for fewest number of stops

Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since ...
• 127
144 views

### Compute the schedule which gives the maximum number of points

Here is the problem statement. Let $E_1,...,E_n$ be a set of $n$ exercises, each taking 1 day to solve, and suppose we have $n$ days available to solve the exercises. Each exercise $E_i$ has a ...
• 127
1 vote
113 views

### Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?

The following approximation algorithm for the Minimal Dominating Set Problem is said by a fellow student to be a 1.5-approximation: Start with empty set $S$ As long as not all vertices are covered: ...
143 views

### Dynamic programming: optimal order to answer questions to score the maximum expected marks

You have $n$ questions in an exam. Question $i$ is answered correctly with probability $p_i > 0$. If question $i$ is answered correctly, you get $R_i$ marks. You can choose to answer the questions ...
• 23
1 vote