## binary search – Greedy approach behind SPOJ Aggressive Cows problem

My doubt is related to the given SPOJ problem
I was able to come up with idea of using Binary Search but struggled with the positioning of the cows. After watching some solutions like this one , almost all of them were placing the first cow at the first stall stating its a greedy approach which works.

I am unable to understand what exactly are we being greedy about as what matters to us is the distance between the cows and not where the cows are placed(i.e we can place 3 cows in the two valid given orders where both give a minimum distance of 2 `(1,4,6)`and `(4,6,10)`)so what is the necessity of placing the first cow at first position.

Also even if there is some reason behind this approach ,how does it guarantee that for a chosen distance `dist` if we can’t place the given number of cows (the fist cow being placed at first stall)with `dist` as the minimum distance then there is no other way of placing the cows(the order in which placing starts from any stall) which would satisfy the conditions.

Posted on Categories Articles

## scheduling – Sequential Tasks with Greedy Algorithm

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 therefore only one task can be executing this part at a time. The second part also has a constraint and only one of the tasks can be executing this at the same time. For task i we know how much time it needs to spend in each part, namely mi for the guarded part, and ai for the part that can be executed in parallel.

The problem is to find a permutation of the tasks such that the time needed to execute all of them is minimized.

Originally I got this question from Greedy sequential/parallel task scheduling, but that got me wondering if there is a greedy solution to this variation of the problem too, where only one task can be executed on the second half at one time as well.

My intuition tells me sort in decreasing order of ai – mi, but I can’t think of a proof for this. I can’t even think of a simple formula for the time it takes to finish all the tasks given some ordering of the tasks. I think that the time it takes is one of choices from $$sum_{i=0}^k m_i + sum_{j=k}^N a_j$$ for some $$j$$ where $$1 leq j leq N$$. Anyone have a closed form formula for the time given some ordering? Also is there a greedy algorithm and proof to go along with it?

Posted on Categories Articles

## Proving correctness for greedy algorithm in string removal problem

Proving correctness for greedy algorithm in string removal problem – Computer Science Stack Exchange

## Sum optimization and greedy approach

I’ve been studying about xgboost and i came across the optimization bellow Can i say that minimizing this summation by minimizing each term as author did is a example of greedy approach?

Posted on Categories Articles

## Determine the approximation factor for greedy vertex cover algorithm

The approximation factor can be $$Omega(log n)$$.

Consider a bipartite graph $$G$$ with a set $$S_L$$ with $$n$$ nodes on the left side. Also consider a collection of sets $$S_{R,1},S_{R,2},dots,S_{R,n}$$ on the right side where each set $$S_{R,i}$$ has an edge to $$i$$ vertices in $$S_{L}$$ and no two vertices in $$S_{R,i}$$s have common edge . So $$lfloor{frac{n}{i}}rfloor$$ in it. So the sum of size of $$S_{R,i}$$s
$$sum_{i=0}^n |S_{R,i}|=Theta(nlog n).$$

After running GreedyVertexCover on this instance, it select all nodes on right side, but the optimal solution was to select all nodes in $$S_L$$.

Consequently, $$frac{ALG(G)}{OPT(G)}=frac{nlog n}{n}=log n.$$
So the approximation factor of your algorithm is $$Omega(log n)$$.

Posted on Categories Articles

## Approximation factor for greedy vertex cover algorithm

The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $$0$$ are left.

Posted on Categories Articles

## approximation – Trouble to understand the proof of greedy algorithm for set cover

Problem definition: Given a universe $$U$$ of $$n$$ elements, a collection of subsets of $$U$$, $$S = {S_1,…, S_k}$$, and a cost function $$c: S to Q^{+}$$. Find a minimum cost subcollection of $$S$$ that covers all elements of $$U$$.

The provided algorithm (Approximation algorithms – Vijay V. Vazirani) Part of the proof where I have trouble to understand My question

I have a difficult time to understand the last in equality, if $$|bar{C}| leq n – k + 1$$, why does $$cfrac{OPT}{|bar{C}|} leq cfrac{OPT}{n – k + 1}$$ hold?

Posted on Categories Articles

## greedy algorithms – Optimality of DSATUR on interval graphs

The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of neighbours already colored, total number of neighbours).

Though not always optimal, this algorithm is already known to be optimal on certain families of graphs, like cycles or bipartite graphs.

An interval graph is a non-directed graph $$G = (V, E)$$ such that there exists a set of intervals $$(I_v)_{vin V}$$ such that $${u, v}in Eiff I_ucap I_vneq emptyset$$.

My question is: is DSATUR optimal for interval graphs?

I already know that there are efficient optimal coloring algorithms for interval graphs, wether you know the corresponding interval set or not, but that is not the question.

My first intuition was that DSATUR was not always optimal, and as a tentative to find a counterexample, I tested 130 millions randomly generated interval graphs, of order between 10 and 20, but none was a counterexample.

That leads me to think that maybe it is optimal, but I have no real idea as to how to prove it.

Posted on Categories Articles

## 0/1 knapsack problem: Greedy Algorithm Counterexample

Consider this counterexample. Suppose the knapsack has a capacity 4. And suppose there are three items:

• Item A with weight 3 and value 5
• Item B with weight 2 and value 3
• Item C with weight 2 and value 3

The optimal solution contains items: B and C, in the knapsack with a total value = 6. However, item A has the highest value/weight ratio: 5/3, which is greater than 3/2.

Posted on Categories Articles

## greedy algorithms – Time to form a complete graph from n vertices given that only k vertices can be used at a time

I know this problem is related to the greedy algorithm and max edges in complete graph but can’t come up a solution.

Problem

You are given two numbers n and k:

n >= k

n is the total # of vertices

k is the maximum number of vertices that can form a complete graph per second

There are no edges initially

how many second does it take to form a complete graph of n vertices ?

Posted on Categories Articles