8
$\begingroup$

We are given $n$ stacks which hold "items" of different colour and a machine that can process multiple items of the same colour in one go. At each step, we can remove one item from the top of each stack and put it into our machine (so effectively the machine can process at most $n$ items in one step - for that to happen, all stacks must have items of the same colour on top). The goal is to process all items in minimal time.

Example input:

One possible solution is a greedy algorithm: at each step, just take as much items as possible and stuff them all into the machine. Unfortunately, the greedy algorithm is not optimal - it produces the following schedule for the example input:

The optimal schedule is the following:

I plan to go with some form of state space search, but maybe there is a more problem-specific and efficient approach? Links to relevant literature appreciated.

$\endgroup$
  • $\begingroup$ At each step, you are allowed to take only one item from the top of each stack (and all the items you put into machine must be of the same colour). So the greedy algorithm produces a non-optimal schedule (see fig. 2). $\endgroup$ – Mikhail Glushenkov May 6 '11 at 21:17
  • $\begingroup$ And you must process all items in order, i.e. take them only from the top. $\endgroup$ – Mikhail Glushenkov May 6 '11 at 21:23
  • $\begingroup$ Ahh. Got it. Interesting problem. I would make an optimal lookup table to decide the first few rows if this were a realtime system. As for exact complexity... prove the optimal for the two column case first. $\endgroup$ – Chad Brewbaker May 6 '11 at 21:45
  • $\begingroup$ The quiestion would be even more interesting, if operating on a set of FIFO lists where you can only peek elements up to particular depth for computation. $\endgroup$ – George Polevoy May 12 '11 at 18:44
7
$\begingroup$

Your problem is equivalent to Shortest Common Supersequence (SCS) and was considered in $[1]$ by the name Scheduling on batch machines with precedence constraints as chains and compatibilities. If items in the problem are of the same color then such problem is in P and can be solved in $O(n^2)$ $[2]$.

What concerns approximability a good source is A compendium of NP optimization problems.

The lastest results on SCS can be found in $[3,4]$.

For practical algorithms see $[5]$ whose author states that "Hybrid MA-BS is a current state-of-the-art technique for the SCSP $[6]$ ".

  1. Brauner N., Naves G. Scheduling chains of operations on a batching machine with disjoint sets of operation compatibility.
  2. Brucker P. Scheduling algorithms (Chapter 8. Batching Problems).
  3. Timkovsky V. G. Some Approximations for Shortest Common Nonsubsequences and Supersequences.
  4. Gotthilf Z. and Lewenstein M. Improved Approximation Results on the Shortest Common Supersequence Problem.
  5. Kubalik J. Efficient stochastic local search algorithm for solving the shortest common supersequence problem.
  6. Blum, C., Cotta, C., Fernandez, A. J., Gallardo, J. E. A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem.
$\endgroup$
  • 1
    $\begingroup$ paper [1] contains an observation i was going to write too: when there are $k$ stacks and $n$ items total, there is a dynamic programming solution in time $O(n^k)$ $\endgroup$ – Sasho Nikolov May 7 '11 at 1:12
2
$\begingroup$

The optimization problems seems to be equivalent to shortest common supersequence as well. The two results I found related to approximating this problem (it is NP-hard in general) are this and this. There are some inapproximability results and much weaker approximation results it seems. The first paper shows $\Omega(\log^\delta n)$ hardness of approximation and a polynomial factor approximation.

Here is a simple fact (I will use your terminology instead of the shortest common supersequence terminology): if there are $k$ colors, then the greedy algorithm (take the items from the color class that has the most available balls) is a $k$ approximation. Say at some step of the optimal we take a set $X$ of $|X| = x$ items, and consider the time step in the algorithm when we first took items from $X$. At that time step in the algorithm there were at least $x$ nonempty stacks (since not all $x$ items from $X$ are taken yet) and by averaging the algorithm took at least $x/k$ items. So the problem has a polytime dynamic programming solution when there are constantly many stacks, and a constant greedy approximation when there are constantly many color classes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.