Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
40 views

Proof of Correctness : Arranging the sheep

I've come across a question in Codeforces contest 719(Div - 3). The problem goes like this : I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
0
votes
0answers
23 views

maximal independent set on grid-based graph proof of approximation ratio

We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight. We use a greedy algorithm that takes in each step maximum weighted ...
2
votes
1answer
24 views

Optimize stacking time series by offsetting start times (feels like a backpack problem?)

Given a time-series of data collected from a single running process that takes 8 hours to complete: Minute GB of Disk Space Used 0 0 1 8 2 15 3 22 ...Etc. It is sampled every minute, for 8 ...
0
votes
0answers
40 views

maximum sum of diameter of tree + leaf removal

Problem: A tree of n nodes is given. Have a sum variable. Choose the leaves furthest from one and other and add their distance(the number of edges between them) to the sum variable. Now remove one of ...
1
vote
1answer
33 views

Find the minimum cost of adding the elements of a set (greedy algorithm)

I'm VERY stuck with this problem: Given a set (with possible repeated elements), the cost of adding two elements $x, y$ is $x + y$. For example, the possible costs of the next set $\{1,2,5 \}$ are: ...
3
votes
1answer
38 views

Expected behavior of an algorithm to minimize rankings

Suppose $n$ students have preferences over $n$ different notebooks. Their preferences can be represented with a square matrix of size $n$ where each column is a different permutation of the vector $[1:...
1
vote
1answer
25 views

Greedy approach suggestions for assigning objects

Suppose there are three categories of people. Type X, Type Y, Type Z. In each type, there are two objects of subtype Type 'a' and type 'b'. For example. X: a1 , a2 , b1 , b2 Y: a3 , a4 , b3 , b4 Z: a5 ...
2
votes
1answer
35 views

k-center problem: proof for Gon algorithm gives a 2-approximation

The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following ...
1
vote
1answer
66 views

Find minimum number of points which intersect overlapping arcs

Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time. I'm having some trouble proving ...
1
vote
1answer
31 views

Does any graph based optimization problem, which have a greedy algorithm, has guarantee that there exist an order which give the optimum

There exist greedy algorithms for vertex coloring like optimization problems. We know that for graph coloring, there is an order of vertices for which greedy coloring produces the optimum results. Is ...
0
votes
1answer
32 views

A problem about Huffman codeword

Under Huffman Encoding, what circumstances codeword length of each character be equal?(suppose number of character is power of 2) I think if all frequency of characters is same then codeword length ...
1
vote
1answer
58 views

Greedy algorithm for maintaining drugs

Given $n$ drugs such that each drug $d_i$ should maintain in interval $[c_i,h_i]$.We want to minimize number of containers to maintain medicines in compatible interval. My answer is as follows: I use ...
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 ...
4
votes
1answer
110 views

Hamiltonian path greedy and anti-greedy algorithms

I had this question on a problem set recently, but I wasn't sure how to solve it. Given a complete weighted undirected graph $G$, here are two "algorithms" to find a Hamiltonian path: ...
0
votes
0answers
89 views

Finding name of a specific problem

Input : $x \in \mathbb Z$ and $a_1,a_2,\dots,a_n \in \mathbb N$. Output : $b_1,b_2,\dots,b_n \in \mathbb Z$ such that $\sum_{i} a_i b_i=x$ and $\sum_{i}|b_i|$ is minimized. Main question is, can we ...
0
votes
0answers
53 views

Need help with a very specific Greedy Algorithm. Are there fast solutions?

i need help for a specific problem i have at work. You have N number of rows in an array, each with some distribution of Numbers that range from 0 to N.Given an array of size 1000: Row 1 might look ...
0
votes
0answers
29 views

Minimum cost bin assignment

I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but ...
1
vote
1answer
31 views

Must an optimization problem with a greedy algorithm belong to P?

If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
1
vote
2answers
64 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 ...
0
votes
1answer
25 views

Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups [duplicate]

Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time ...
0
votes
1answer
58 views

What Makes an Algorthim Greedy [Graph Coloring Algorithm]

I have a simple graph G = (V,E) and each vertex has a range [a,b].Every two vertices are connected only if [a_1,b_1] and [a_2,b_2] have a common subrange. Each range of vertex is rV1 = [0,5] rV2 = [1,...
4
votes
1answer
47 views

Is the following Greedy algorithm to generate Gray Codes always correct?

I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites)....
2
votes
2answers
83 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, $...
0
votes
1answer
28 views

How to (Efficiently) Sort a List of Items with Parent/Child Relationship

I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member ...
1
vote
1answer
45 views

Maximum Independent Set of special Directed Graph

I was given this special type of Directed Graph and was asked to find it's Maximum Independent Set. Graph Properties : Graph has $N$ vertices and $N$ edges There can be no edge from a vertex $v$ to ...
3
votes
1answer
110 views

Greedy algorithm for subset sum on powers of 2

I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after ...
0
votes
0answers
21 views

Rearrange string k distance Apart

The question statement is as follows: Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. All input strings are ...
1
vote
0answers
18 views

Greedy Best-First Search Performance for Tree and Graph Space

I am currently reviewing the GBFS algorithm and when looking at its completeness I am confused between the difference of it being not optimal in Tree Search for Finite and Infinite Spaces that it is ...
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
0
votes
2answers
52 views

Highest Product of X Items

🧩 How do you find the highest product of X items? This should optimize for runtime complexity and protect from overflows from large products. Inputs An array of both positive and negative Ints ...
2
votes
1answer
43 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
32 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 &...
1
vote
0answers
32 views

Does the existence of a matroid structure imply that the greedy algorithm is optimal?

I was going through the topic of matroid structures for the problems like Activity selection ,minimum spanning tree. I also came to know how to solve if a problem exhibits matroid structure. The ...
0
votes
0answers
29 views

Greedy Proof: For coin denomination systems, faster proof to ensure greedy solution yields the optimal solution

I have reasons to believe that there is a faster way to confirm, that for coin denomination systems if the greedy solution yields the optimal solution or not. I believe that if you check that for all ...
2
votes
1answer
486 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 ...
1
vote
1answer
43 views

Serving $k$ customers with bounded time window

A person provides a service and he/she can serve $k$ clients each minute. Now, client number $i$ comes at the beginning of minute $a_{i}$ and waits $w_{i}$ minutes to receive the service and if they ...
0
votes
1answer
43 views

Ordering the tasks to minimize penalties

So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows: In your calendar you have an $L$ list of all the tasks you need to complete today. ...
-1
votes
1answer
86 views

Correctness proof of a greedy approximation algorithm

How do I prove the correctness of this algorithm?
2
votes
0answers
39 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 ...
0
votes
2answers
81 views

Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?

There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is: There are n tasks, each task ...
0
votes
1answer
37 views

Mathematical expression for the quantity that we are maximising in the stock buying and selling problem

Problem Statement: Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete as many ...
0
votes
2answers
75 views

What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]

I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, ...
-1
votes
1answer
47 views

Prove following statement about Kruskal Algorithm

Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
0
votes
0answers
51 views

Find the maximum number of valid cartesian coordinates

Given a list X containing m number of x coordinates and a list Y containing m number of y coordinates. The coordinate (x, y) is valid if and only if the difference between x and y is less than or ...
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 - ...
0
votes
0answers
19 views

Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
0
votes
1answer
87 views

Binary string satisfying several constraints

I'm trying to solve this problem, but without success. Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...
1
vote
0answers
46 views

Algorithm for summation with lowest maximum temporary sum

I've got this problem on my last exam, which I struggle to deal with. Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
3
votes
2answers
240 views

Difficulty in understanding the proof of the lemma : “Matroids exhibit the optimal-substructure property”

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma ...
0
votes
1answer
487 views

Greedy sequential/parallel task scheduling

We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and ...

1
2 3 4 5
7