People who code: we want your input. Take the Survey

Questions tagged [greedy-algorithms]

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

76 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
212 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 ...
6
votes
0answers
156 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 ...
4
votes
1answer
324 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 ...
4
votes
1answer
102 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 ...
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, ...
3
votes
0answers
245 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 ...
2
votes
0answers
46 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 ...
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 - ...
2
votes
0answers
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$ ...
2
votes
0answers
82 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 ...
2
votes
0answers
49 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 ...
2
votes
1answer
429 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
2
votes
0answers
259 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 ...
2
votes
0answers
191 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 ...
2
votes
0answers
520 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 ...
2
votes
0answers
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) ...
2
votes
0answers
732 views

Single machine job scheduling (Greedy heuristic)

Here is a variation of a job-scheduling Problem. Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge ...
2
votes
0answers
672 views

Other greedy choices to solve activity selection problem

I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities. But surely ...
1
vote
0answers
11 views

How to find optimal greedy algorithm?

This is an intriguing question for which I want to find an optimal solution: Each week, you can choose to work ONLINE $(ON)$ or in person $(WR)$ in your department's office. If you attend work online ...
1
vote
0answers
27 views

Which algorithms exhibits Greedy Choice Property but not Optimal Substructure Property

After a few courses using CLRS, I still have not been able to find a satisfying answer to the title question. This answer suggests Hoffman trees. But here the greedy choice is the two subtrees with ...
1
vote
0answers
19 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 ...
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 ...
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 ...
1
vote
0answers
28 views

Remove vertices to get k-connected components

In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?
1
vote
0answers
183 views

Greedy algorithm to divide objects into the lowest number of groups of a maximum size

I have n objects of independent size s, and need to group them so that the sum of the sizes of each group is smaller than a given maximum size, and the number of groups is the smallest possible. I ...
1
vote
0answers
47 views

Looking for an algorithm or similar mathematical problem for trading ownerships in shared property

Suppose there is $N$ property. Each property is owned by multiple person. (they have shared ownership) For example: $Person_1$ owns 22% of $Property_1$, $Person_2$ owns 35% of $Property_1$ and $...
1
vote
0answers
34 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 ...
1
vote
0answers
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 ...
1
vote
0answers
46 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 ...
1
vote
0answers
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?
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
383 views

With restrictions, can the knapsack puzzle be solved with a greedy algorithm?

I know that with the knapsack problem in general, there is no known greedy algorithm to solve it. But, say we add the following constraints: • All items have values equal to their weights (for all $...
1
vote
0answers
202 views

Information gain vs Gini impurity, for Random Forest?

I was researching about the supervised algorithm called Random Forest, that made me begin to study about decision trees, and how to induce them from a set, in order to create several predictors. My ...
1
vote
0answers
155 views

find max k sequence - is it greedy?

The original problem statement is: Given a sequence of numbers $A[1..n]$, find $k < n$ consecutive numbers such that the sum of these $k$ numbers is maximized where $k$ is a positive ...
1
vote
0answers
196 views

convex hull for unsorted vertices solved by graham scan algorithm

can graham scan algorithm work with convex hull vertices when vertices are not sorted? I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by ...
1
vote
0answers
55 views

Conjecture about a matrix column swapping challenge problem

So here is the challenge problem statement: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1512 Basically, given a 0/1 matrix, you ...
1
vote
0answers
48 views

How to maximize the number of buyers in a shop?

There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items ...
1
vote
0answers
841 views

Fast algorithm for finding a minimum cost path through points in the plane

Consider the following problem: There are $n$ points in the plane. Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way ...
0
votes
0answers
6 views

Minimum Number of Refueling Stops with DP

This is a question from Leetcode and i wanted to solve with Dynamic Programming. upon seeing the solution, i am not able to get the intution behind the logic. I was able to understand the solution ...
0
votes
0answers
35 views

Filling Two Knapsacks with greedy algorithm

I've got the next problem, where I have two, instead of one, knapsacks. Formally, we have items $1, \ldots , n$ and each item $i$ has a positive integer weight $w_i \in \mathbb{N}$ and a positive ...
0
votes
0answers
21 views

Is correctness implied by an optimality proof?

New to proofs (in the context of analysis of algorithms). I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
0
votes
0answers
25 views

Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem. I understand how the solution is implemented but,...
0
votes
0answers
25 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 ...
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 ...
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
54 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 ...
0
votes
1answer
60 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,...
0
votes
0answers
23 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 ...