Questions tagged [greedy-algorithms]

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

57 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
1answer
317 views

The heaviest induced subgraph problem

I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
6
votes
0answers
145 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
148 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
247 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
93 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
225 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
22 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
64 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
37 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
229 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
2
votes
0answers
146 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
141 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
489 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
1k 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
715 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
627 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
25 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
64 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
39 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
2answers
186 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
0answers
59 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
96 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
48 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
333 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
358 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
0answers
164 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
113 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
188 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
53 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
830 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
20 views

How to prove optimal substructure for Lecture Hall assignment problem?

In CLRS, an approach has been given to prove the optimal substructure and the correctness of the greedy algorithm for the activity selection problem. In the Lecture Hall assignment problem, we sort ...
0
votes
0answers
32 views

Catching ball - finding the maximum number of caught balls

I'm attempting to solve the following problem: Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which ...
0
votes
0answers
109 views

Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank: Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a ...
0
votes
0answers
16 views

How to detect self loop in graph using greedy algorithm if given list of number of degrees

if you are given list of n integers that represents the degree of a graph. How to detect if there self loop in the graph using greedy algorithm.
0
votes
0answers
44 views

Job Scheduling with deadline with $nlogn$ algorithm

We know that there is a Greedy algorithm for scheduling of $n$ jobs which each job has its own deadline and profit. In greedy algorithm, we sort the set by their profit descendant, And if a job can ...
0
votes
0answers
23 views

Activity Selection with changable start time

I have been studying a problem in my work and I have reduced my problem to likewise Activity Selection problem. It is a problem that I know and I am familiar with the greedy solution. However, in my ...
0
votes
0answers
115 views

How does ordering paradigm differs from subset paradigm in greedy method?

What is the difference between subset paradigm and ordering paradigm of greedy method approaches? More precisely I didn't understood how does the ordering paradigm differs from subset paradigm? ...
0
votes
0answers
37 views

Improving on Monte-Carlo

Can I improve on a Monte-Carlo search for the problem, described? So I have a graph/network consisting of segments a1, a2, ..., b1, b2, ..., and c1, c2, ... For all the underlying segments there is ...
0
votes
0answers
39 views

Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
0
votes
0answers
45 views

Interval scheduling with shared resources between steps

I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each ...
0
votes
0answers
117 views

Maximum matching blossom algorithm

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just ...
0
votes
1answer
314 views

Maximize the sum of chosen numbers

I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem. Suppose there is a game with 2 players, A and B and a ...
0
votes
0answers
36 views

findining the smallest sum of squared lengths of the intervals I_{k}

Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals $I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
0
votes
0answers
38 views

Algorithm to check if exists a valid streaming sequence in O(n)?

Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
0
votes
0answers
75 views

Table of incompatible turns in an intersection (steps to writing a program)

I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads. ...
0
votes
0answers
509 views

Proving a greedy algorithm

Hey so I'm studying for a midterm and I've run into this problem in the material. I'm not sure how to go about solving it. If I use regular induction in part a, I get something a bit tautological. Any ...
0
votes
0answers
77 views

Generating a Covering Array Matrix with Simulated Annealing

I've been reading the following paper to understand how I can develop a non deterministic algorithm for test cases generation https://www.researchgate.net/publication/293043297_A_two-...
0
votes
0answers
1k views

What algorithm does OLA and UBER use for allotting taxis

More specifically : lets say i have 5 taxis , each available for booking at t=0; i have two days (48 hrs) with me how can I maximise their booking . I may not be able to clarify the question , this ...
0
votes
0answers
367 views

Interval scheduling, unclear greedy proof

I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem. The proof that I am ...