<p>First, the problem discription:</p>

<p>For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of length $0$ such that in the end all the tasks are put in the queues and both queues has length $2n$. Let $cost$ be 0 at first. For each task $a_i$ that has value $1$, we add its index in the queue to the $cost$.
The objective is to minimize the $cost$.</p>

<p>Example, the sequence of tasks is $10101010$, and we put the $1$th task in queue $1$, the $2$th task in queue $1$, the $3$th task in queue $2$, the $4$th task in queue $1$, the $5$th task in queue $2$, the $6$th task in queue $1$, $7$th task in queue $2$, the $8$th task in queue $2$, then queue $1$ will has task sequence $1000$ and queue $2$ will has task sequence $1110$, so the $cost$ is $(1)+(1+2+3)=7$.</p>

<p>Then we describe the greedy algorithm with parameter $0\le k\le 2n$：</p>

<p>It first puts the first $k$ tasks sequentially to the end of queue $1$. Then for $i=k+1,\dots$, if $a_i=1$ it puts the $i$th task into a queue with smaller length, else it puts the $i$th task into a queue with bigger length until one of the queues is full(it has length $2n$). Finally it puts the rest of tasks sequentially to the end of the non-full queue.</p>

<p>The question is proving the best greedy algorithm(over choices of $k$) gives the optimal cost for any $4n$ length sequence. I have many simulation results that support this statement and haven't found a proof yet.</p>

CC BY-SA 3.0
2013-06-15T11:38:39.350Z
Does your simulation use random costs? If so, the greedy algorithm might be optimal for all your instances, but not for general instances.
Peter Shor 
CC BY-SA 3.0
2013-06-15T12:09:49.043Z
@PeterShor: One of my simulation enumerates all sequences of length 20 (total number $2^{20}$) and it shows that greedy algorithm is optimal for these sequences. And you are right that for sequences with bigger length, it might not be optimal. But I guess it is.
caozhu
CC BY-SA 3.0
2013-06-15T12:26:51.097Z
That simulation is indeed convincing.
Peter Shor 
CC BY-SA 3.0
2013-06-15T17:03:58.673Z
Is there a good example for why $k=0$ yields a suboptimal solution?
Suresh Venkat
CC BY-SA 3.0
2013-06-15T20:08:43.203Z
what's special about length $4n$? does it fail for $2n$?
Chao Xu
CC BY-SA 3.0
2013-06-15T20:10:36.500Z
Doesn't it follow from a simple exchange argument? Essentially proving inductively and then using the exchange saying that you are moving towards an optimal solutions at the i^{th} step
NAg
CC BY-SA 3.0
2013-06-16T02:26:51.200Z
@ChaoXu: Nothing special. I think the statement also holds for $2n$.
caozhu
CC BY-SA 3.0
2013-06-16T02:41:26.267Z
@SureshVenkat: For example, task sequence 101010101010 makes greedy algorithm with k=0 a sub optimal solution. At the end of the algorithm, the two queues will be $100000$ and $111110$, making the cost $(1)+(1+2+3+4+5)=16$. When $k=3$ or $k=4$, two queues will be $101000$ and $111010$, making the cost $(1+3)+(1+2+3+5)=15<16$. Thus $k=0$ is suboptimal in this case.
caozhu
CC BY-SA 3.0
2013-06-16T02:53:25.180Z
@NAg: I don't quite understand what you mean. Could you be more specific on how you do the induction?
caozhu
<ds.algorithms><optimization><lower-bounds><proofs><scheduling>
Proving greedy algorithm is optimal for a scheduling problem
caozhu
# Proving greedy algorithm is optimal for a scheduling problem

(Asked by: username_0 on 2013-06-15)

First, the problem discription:

For a sequence of $4n$ tasks, $a\_1a\_2\dots a\_{4n}$, where $a\_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of length $0$ such that in the end all the tasks are put in the queues and both queues has length $2n$. Let $cost$ be 0 at first. For each task $a\_i$ that has value $1$, we add its index in the queue to the $cost$.
The objective is to minimize the $cost$.

Example, the sequence of tasks is $10101010$, and we put the $1$th task in queue $1$, the $2$th task in queue $1$, the $3$th task in queue $2$, the $4$th task in queue $1$, the $5$th task in queue $2$, the $6$th task in queue $1$, $7$th task in queue $2$, the $8$th task in queue $2$, then queue $1$ will has task sequence $1000$ and queue $2$ will has task sequence $1110$, so the $cost$ is $(1)+(1+2+3)=7$.

Then we describe the greedy algorithm with parameter $0\le k\le 2n$：

It first puts the first $k$ tasks sequentially to the end of queue $1$. Then for $i=k+1,\dots$, if $a\_i=1$ it puts the $i$th task into a queue with smaller length, else it puts the $i$th task into a queue with bigger length until one of the queues is full(it has length $2n$). Finally it puts the rest of tasks sequentially to the end of the non-full queue.

The question is proving the best greedy algorithm(over choices of $k$) gives the optimal cost for any $4n$ length sequence. I have many simulation results that support this statement and haven't found a proof yet.

**Tags:** ds.algorithms, optimization, lower-bounds, proofs, scheduling

> **Comments:**
> **username_1**: Does your simulation use random costs? If so, the greedy algorithm might be optimal for all your instances, but not for general instances.  
> **username_0**: @PeterShor: One of my simulation enumerates all sequences of length 20 (total number $2^{20}$) and it shows that greedy algorithm is optimal for these sequences. And you are right that for sequences with bigger length, it might not be optimal. But I guess it is.  
> **username_1**: That simulation is indeed convincing.  
> **username_2**: Is there a good example for why $k=0$ yields a suboptimal solution?  
> **username_3**: what's special about length $4n$? does it fail for $2n$?  
> **username_4**: Doesn't it follow from a simple exchange argument? Essentially proving inductively and then using the exchange saying that you are moving towards an optimal solutions at the i^{th} step  
> **username_0**: @ChaoXu: Nothing special. I think the statement also holds for $2n$.  
> **username_0**: @SureshVenkat: For example, task sequence 101010101010 makes greedy algorithm with k=0 a sub optimal solution. At the end of the algorithm, the two queues will be $100000$ and $111110$, making the cost $(1)+(1+2+3+4+5)=16$. When $k=3$ or $k=4$, two queues will be $101000$ and $111010$, making the cost $(1+3)+(1+2+3+5)=15<16$. Thus $k=0$ is suboptimal in this case.  
> **username_0**: @username_4: I don't quite understand what you mean. Could you be more specific on how you do the induction?  

---

## 0 answers

