You are not logged in. Please login at www.codechef.com to post your questions!

×

CAKES - Editorial

0
1

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

This question is marked "community wiki".

asked 29 Nov '12, 11:27

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

edited 22 Feb '13, 23:36

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,642
×847
×11
×7

question asked: 29 Nov '12, 11:27

question was seen: 1,952 times

last updated: 22 Feb '13, 23:36