Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
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 ...
1
vote
1answer
114 views

center selection problem: Simple greedy algorithm

I am trying to understand the following text which defines a greedy algorithm for center selection problem: It would put the first center at the best possible location for a single center, then ...
1
vote
1answer
1k views

Selecting elements from two arrays to get a target sum

Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer. Design an algorithm to solve the following problem. For each index $i$ ($1\leq i \leq n$)...
1
vote
1answer
191 views

Converting a greedy algorithm to a dynamic programming algorithm

Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be: First, find a maximum indpendent set of ...
1
vote
1answer
41 views

Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?

I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, ...
1
vote
1answer
657 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 ...
1
vote
1answer
6k views

How does the nearest insertion heuristic for TSP work?

In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson ...
1
vote
3answers
1k views

Stable matching problem is greedy or Dynamic?

Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.
1
vote
1answer
187 views

Greedy algorithm: Minimizing the maximum of a list

Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last ...
1
vote
1answer
778 views

Optimizing greedy solution for choice game

Consider the following game: Two players choose numbers from a sequence of integers with even number of elements. The two can only choose from either the front or the end of the sequence. The purpose ...
1
vote
1answer
413 views

Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is ...
1
vote
2answers
2k views

How to prove greedy algorithm for number partitioning?

the partition problem (or number partitioning1) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the ...
1
vote
1answer
2k views

People crossing a bridge (a proof for a greedy algorithm)

The problem Some people are crossing a bridge. Each one takes a different time to pass. Assume the people are sorted by their passing time increasingly. These are the conditions of crossing the ...
1
vote
2answers
187 views

Greedily Schedule Events based on value/hours

Suppose we are given a list of $n$ events $E = \{E_1, E_2, \ldots, E_n\}$ where each $E_i$ is represented by $(s_i, h_i, v_i)$ or $(start, hours, value)$. So if you attend an entire event that lasts ...
1
vote
1answer
12k views

Proving greedy choice property of fractional knapsack

A typical way of proving the greedy choice property of the fractional knapsack problem is as follows: From Slide 5 of this link: Given: A set of items $I = \{I_1,I_2..I_n\}$ with weights $\{w_1,w_2 ....
1
vote
1answer
32 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
1answer
78 views

Proof for an algorithm to minimize $\max(a, b, c) - \min(a, b, c), a \in A, b \in B, c\in C$, A, B, C are arrays in ascending order

Problem Statement I came across this problem here. For given arrays $A$, $B$ and $C$ arranged in ascending order, we need to minimize the objective function $f(a, b, c) = \max(a, b, c) - \min(a, b, c)...
1
vote
2answers
165 views

Proof by contradiction for greedy algorithms

I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never ...
1
vote
2answers
194 views

Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines

I'm trying to prove a greedy algorithm works for a specific problem: You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run ...
1
vote
3answers
425 views

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem: An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
1
vote
1answer
96 views

Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

The problem is in this other question. Why does this always work? It's not clear to me how one would use induction. For $n = 3$, a quick calculation shows it works, however, I don't think it ...
1
vote
1answer
251 views

Carpet into Box

Given a carpet of size a * b [length * breadth] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or ...
1
vote
2answers
230 views

Minimum spanning tree such that one edge can be minimised

During a computer coding exam, I have encountered such a problem. Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
1
vote
1answer
557 views

How this proof of fractional knapsack works?

I don't understand a step in my book proving the fractional knapsack problem: Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by greedy, ...
1
vote
1answer
1k views

Greedy algorithm to find Minimum Dominating Set in a tree

Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
1
vote
1answer
898 views

Proof of a greedy algorithm concerning “Buy and Resell Problem”

"Buy and Resell Problem" can be described in the following way: There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from ...
1
vote
1answer
311 views

Why this greedy algorithm does not return the optimal solution to this NP-hard problem?

Problem: In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective ...
1
vote
2answers
68 views

Online set filling with redistributions

Edited: Suppose we have 4 sets $A, B, C, D $ which can can hold a maximum of two elements, each. Now, elements ($E_i$) arrive serially with properties such as: ...
1
vote
1answer
131 views

Can LP for matroid polytopes be solved using the greedy algorithm?

For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, ...
1
vote
2answers
260 views

Element wise product sum of two arrays

I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving ...
1
vote
1answer
1k views

Does a greedy strategy exist for this instance of the Bin Packing Problem?

I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 ...
1
vote
1answer
1k views

Huffman code optimal substructure property

I am learning about Greedy Algorithms and we did an example on Huffman codes. To prove the correctness of our algorithm, we had to have the greedy choice property and the optimal substructure property....
1
vote
1answer
2k views

Dynamic programming VS Greedy Algroithms [closed]

I have two True or False questions in my practice test that are related but I am unsure about: ...
1
vote
1answer
71 views

How to prove the my greedy algorithm for placing guards?

Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images ...
1
vote
1answer
34 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: ...
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 ...
1
vote
1answer
73 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 ...
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 ...
1
vote
1answer
52 views

Problem related to set partitioning

Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$ Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one ...
1
vote
1answer
307 views

Maximum number of similar groups of a given size that can be made from a given array

I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$. I need to find the maximum number of groups with the ...
1
vote
1answer
37 views

Trivial solution to the Continuous Knapsack problem

I am a bit puzzled as to why the continuous knapsack problem is a non-trivial problem https://en.m.wikipedia.org/wiki/Continuous_knapsack_problem Using the terminology in the Wikipedia link above, ...
1
vote
2answers
102 views

Putting as many items as possible with weight and size limit

I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice. Any item has an item weight of Iw and item size of <...
1
vote
1answer
65 views

Minimum Spanning Tree with one particular edge minimised(continued)

I have recently encountered a coding problem, specifically, the CCC problem S4. In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
1
vote
1answer
54 views

Trying to understand the question(well spaced points ?) better

Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
1
vote
1answer
105 views

What is the optimal way to solve the following optimization problem

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$. We need to compute the function $F(L)$ using the least number of transformations/...
1
vote
1answer
92 views

Variant of interval scheduling with varying task durations

I am probably just missing the correct term for my problem to find the solution but here it goes: I have a set of tasks with a given duration and an interval for each task in which it has to be ...
1
vote
1answer
274 views

Algorithm to organize a tournament where the team componentes change each round

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
1
vote
2answers
360 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 ...
1
vote
1answer
64 views

Candy Problem for k size window

I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) ...

1 2 3
4
5
7