<p>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 <a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v24/i5/p1122_s1" rel="nofollow">this</a> and <a href="http://portal.acm.org/citation.cfm?id=642130" rel="nofollow">this</a>. There are some inapproximability results and much weaker approximation results it seems. The <a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v24/i5/p1122_s1" rel="nofollow">first paper</a> shows $\Omega(\log^\delta n)$ hardness of approximation and a polynomial factor approximation.</p>

<p>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. </p>

CC BY-SA 3.0
2011-05-07T01:54:24.873Z
2011-05-07T01:54:24.873Z
Sasho Nikolov
<p>Your problem is equivalent to <em>Shortest Common Supersequence</em> (SCS) and was considered in <span class="math-container">$[1]$</span> by the name <em>Scheduling on batch machines with precedence constraints as chains and compatibilities</em>. If items in the problem are of the same color then such problem is in P and can be solved in <span class="math-container">$O(n^2)$</span>  <span class="math-container">$[2]$</span>.</p>
<p>What concerns approximability a good source is <em><a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/node165.html" rel="nofollow noreferrer">A compendium of NP optimization problems</a></em>.</p>
<p>The lastest results on SCS can be found in <span class="math-container">$[3,4]$</span>.</p>
<p>For practical algorithms see <span class="math-container">$[5]$</span> whose author states that &quot;Hybrid MA-BS is a current state-of-the-art technique for the SCSP <span class="math-container">$[6]$</span> &quot;.</p>
<ol>
<li>Brauner N., Naves G. <a href="https://hal.science/hal-00264402/" rel="nofollow noreferrer">Scheduling chains of operations on a batching machine with disjoint sets of operation compatibility</a>.</li>
<li>Brucker P. Scheduling algorithms (Chapter 8. Batching Problems).</li>
<li>Timkovsky V. G. <a href="https://doi.org/10.1007/978-3-540-89097-3_25" rel="nofollow noreferrer">Some Approximations for Shortest Common Nonsubsequences and Supersequences</a>.</li>
<li>Gotthilf Z. and Lewenstein M. <a href="https://doi.org/10.1007/978-3-642-03784-9_27" rel="nofollow noreferrer">Improved Approximation Results on the Shortest Common Supersequence Problem</a>.</li>
<li>Kubalik J. <a href="https://doi.org/10.1145/1830483.1830529" rel="nofollow noreferrer">Efficient stochastic local search algorithm for solving the shortest common supersequence problem</a>.</li>
<li>Blum, C., Cotta, C., Fernandez, A. J., Gallardo, J. E. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.75.9732" rel="nofollow noreferrer">A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem</a>.</li>
</ol>

CC BY-SA 3.0
2011-05-07T01:12:37.870Z
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)$
Sasho Nikolov
CC BY-SA 4.0
2011-05-06T23:39:29.407Z
2023-05-16T11:50:29.037Z
2023-05-16T11:50:29.037Z
Oleksandr Bondarenko
<p>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 <em>one</em> item from the <em>top</em> 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.</p>

<p>Example input:</p>

<p><img src="https://i.sstatic.net/wH4I4.png" width="100"></p>

<p>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:</p>

<p><img src="https://i.sstatic.net/Izs0t.png" width="100"></p>

<p>The optimal schedule is the following:</p>

<p><img src="https://i.sstatic.net/xs3Tp.png" width="100"></p>

<p>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.</p>

CC BY-SA 3.0
2011-05-06T21:17:21.470Z
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).
Mikhail Glushenkov
CC BY-SA 3.0
2011-05-06T21:23:37.583Z
And you must process all items in order, i.e. take them only from the top.
Mikhail Glushenkov
CC BY-SA 3.0
2011-05-06T21:45:19.407Z
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.
Chad Brewbaker
CC BY-SA 3.0
2011-05-12T18:44:18.127Z
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.
George Polevoy
<ds.algorithms><reference-request><scheduling>
Is this a known combinatorial optimization/scheduling problem?
Mikhail Glushenkov
# Is this a known combinatorial optimization/scheduling problem?

(Asked by: username_0 on 2011-05-06)

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:

![](https://i.sstatic.net/wH4I4.png)

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:

![](https://i.sstatic.net/Izs0t.png)

The optimal schedule is the following:

![](https://i.sstatic.net/xs3Tp.png)

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.

**Tags:** ds.algorithms, reference-request, scheduling

> **Comments:**
> **username_0**: 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).  
> **username_0**: And you must process all items in order, i.e. take them only from the top.  
> **username_1**: 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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_4 on 2011-05-06. Score: 7 | Accepted answer

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](https://www.csc.kth.se/%7Eviggo/wwwcompendium/node165.html)*.

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](https://hal.science/hal-00264402/).
2. Brucker P. Scheduling algorithms (Chapter 8. Batching Problems).
3. Timkovsky V. G. [Some Approximations for Shortest Common Nonsubsequences and Supersequences](https://doi.org/10.1007/978-3-540-89097-3_25).
4. Gotthilf Z. and Lewenstein M. [Improved Approximation Results on the Shortest Common Supersequence Problem](https://doi.org/10.1007/978-3-642-03784-9_27).
5. Kubalik J. [Efficient stochastic local search algorithm for solving the shortest common supersequence problem](https://doi.org/10.1145/1830483.1830529).
6. Blum, C., Cotta, C., Fernandez, A. J., Gallardo, J. E. [A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.75.9732).

> **Comments:**
> **username_3**: 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)$  

---

### Answer by username_3 on 2011-05-07. Score: 2

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](http://epubs.siam.org/sicomp/resource/1/smjcat/v24/i5/p1122_s1) and [this](http://portal.acm.org/citation.cfm?id=642130). There are some inapproximability results and much weaker approximation results it seems. The [first paper](http://epubs.siam.org/sicomp/resource/1/smjcat/v24/i5/p1122_s1) 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.


---

