# PROBLEM LINKS

Practice

Contest

# DIFFICULTY

CHALLENGE

# EXPLANATION

As is the case with many challenge problems, this problem is NP-hard. It is often called the "Concurrent Open Job Shop" problem in research

literature. There is, however, one simplification that can be made. That is, we can restrict our attention to solutions where the cakes are scheduled

in the same order by all bakers for the following reason. Consider a solution S and say baker i works the longest overall (i.e. has the largest sum

of preparation times) and processes cake j last in S. Adjust S by moving cake j to the end of every baker's schedule while not changing the

relative order of the remaining cakes. The completion time of every cake j' != j is not decreased since their completion time by each individual

baker does not decrease. The completion time of cake j does not decrease since baker i worked the longest so all other bakers i' != i still

complete cake j no later than baker i. Recursively apply these arguments to the remaining cakes j' != j.

The problem can, however, be approximated somewhat well. The following O(n * (n+m)) algorithm finds a solution whose weighted completion

time is no more than 2 times the optimum. Denote the weight of customer j by w(j) and the processing time of cake j by baker i by p(j,i). Let I

be the baker that will work the longest (i.e. maximizes p(j _ 1, i) + p(j _ 2, i) + ... + p(j _ n, i)) and let j be the cake j that minimizes w(j)/p(j,i). Add

cake j to the end of the schedule we will recursively compute on the remaining cake. For each job j' != j, update w(j') := w(j') - w(j) * p(j',i)/p(j,i).

Recursively compute a schedule on the remaining cakes j' != j according to these new weights and add cake j to the end of this schedule.

The arguments showing why this is a 2-approximation are subtle and can be found in [1]. Assuming P != NP, one cannot approximate this problem

within any constant better than 6/5 with a polynomial-time algorithm

[1]. Finally, even approximating this problem within a constant better than 2 will refute a fundamental open conjecture known as the

"Unique Games Conjecture" (independently shown in [2] and [3]). So, while this

conjecture is still open we do not know how to guarantee a better-than-2 approximation in polynomial time.

[1] M. Mastrolilli, M. Queyranne, A. Schulz, O. Svensson, and N. Uhan, Minimizing the sum of weighted completion times in a concurrent open shop.

Operations Research Letters (2010), doi:10.1016/j.orl.2010.04.011

[2] N. Bansal and S. Khot, Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. Preprint available at Subhash's

page http://cs.nyu.edu/~khot/

[3] A. Kumar, R. Manokaran, M. Tulsiani, N. Vishnoi, On LP-based approximability for strict CSPs. Preprint available at

http://arxiv.org/abs/0912.1776

asked
**29 Nov '12, 11:27**

0★admin ♦♦

19.8k●350●498●541

accept rate:
36%