New answers tagged greedy-algorithms
3
The formalized problem here is selecting the minimum number of points such that for each temperature interval $\ell_i\in L$ we have at least one point that covers it. Let each interval $\ell_i$ be represented by $(c_i, h_i)$
Order all $\ell_i\in L$ by their $h_i$.
While there are still items that need fridges.
Buy a fridge and set it to $h_1$.
For every ...
0
What you describe is just an approximate algorithm for the Job Shop problem (which is also NP-complete, reduced from Partition -- split a set of integers in two so that both add to the same value, the problem you describe) that can be shown has an approximation ratio of 2. See for example this set of slides for a proof and hints at refinements that get ...
1
As Jeff Erickson says in his book, "greedy algorithms never work". (Except in the --rare-- cases where they do, and they offer simple, efficient approximations to many NP-hard search problems, see for instance Kun's "When Greedy Algorithms are Good Enough: Submodularity and the (1 – 1/e)-Approximation", check also Krause and Golovin's survey for more in-...
0
I'd start with the shortest temperature range, stash everything that fits in it into a refrigerator, rinse and repeat. But a temperature range may overlap several that don't overlap among themselves, among those that do overlap search for a temperature that hits most ranges. This heuristic sounds like it should give a good solution, but I'd first look if ...
2
Yes, this is NP-hard. Since neither the $a_i$ nor the $d_i$ depend on the solution, the problem is equivalent to the problem of minimizing the sum of the completion times of the requests, which is known in the scheduling literature as "$1|r_i|\sum C_i$" and is NP-hard. Reference:
J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker.
Complexity of machine ...
0
It doesn't matter in which order we place the guards, so we can assume that we place the guards in such an order that each guard covered the first artwork from the right that isn't covered yet (since there must be a guard covering that artwork).
The guard can be placed anywhere from 5m to the left of the artwork to 5 to the right. Wherever we place him, ...
0
Let us prove your greedy algorithm is optimal in the sense of the least number of guards returned by simple reasoning.
Consider all "closest artwork"s found by your greedy algorithm. The algorithm ensures that each neighboring pair of them is over 10 meters apart. So any two of them are over 10 meters apart, which means one guard can monitor at most one of ...
1
You can achieve this per induction over the position of the last artwork. Note that in the optimal strategy the guard must be put 5 meter ahead of the left most artwork and not exactly at it.
In the induction step you have to consider an additional artwork and distinct two cases, whether it is covered by the last fixed guard or not. If it is, you do not ...
2
Brooks' theorem states that every connected graph $G$ with maximum degree $\Delta$ can be colored (in linear time) using at most $\Delta + 1$ colors. In fact, the graphs that require $\Delta + 1$ colors are precisely complete graphs and odd cycles.
You state that we have a connected graph $G$ with an odd number of vertices and we want to color $G$ with $k$ ...
Top 50 recent answers are included
