3
$\begingroup$

Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that we must complete. The task at vertex $v$ takes $q_v > 0$ minutes for $v \neq 0$, and we must complete all tasks. We start at Vertex $0$, and we have $q_0 = 0$.

It will obviously take us exactly $\sum_{i = 1}^{n} q_i$ total time for us to complete all of the tasks on our own (it doesn't take any time to traverse the edges). However, suppose we have a single helper. We are allowed to dispatch the helper at any node (say $v$), and we can leave the node, go work on other tasks, and pick up the helper after $q_v$ minutes to drop it off at another node. A caveat is that the helper cannot move on its own; it must be picked up and dropped off.

Is there some sort of algorithm that allows one to find the best strategy (i.e., one that minimizes the total time) when we are allowed one helper?

A naive strategy would be a greedy strategy that always drops off the helper at the vertex with the largest $q_i$. It seems like this would minimize the time that the helper is idle; however, I have no reason to believe that this is optimal.

Does anyone have any suggestions or heuristics for an approximate solution?

$\endgroup$
5
$\begingroup$

Hardness

The problem is strongly $NP$-hard so there likely is no fast algorithm solving it.

Consider the 3-Partition problem wherein we are given $3n$ distinct integers $x_1,\ldots, x_{3n}$ and an integer $T$ such that $T/4< x_i< T/2$ and asked to decide whether we can group the $3n$ integers into $n$ groups of $3$ integers with sum equal to $T$ for each triple.

We create an instance of the problem with $4n$ tasks, $3n$ of those tasks having length $x_i$ (one for each $1\leq i\leq 3n$) and $n$ tasks having length $T$.

There exists a solution with no idle time if and only if the 3-Partition instance is solvable. Clearly, if there is a solution to the 3-Partition instance there is a solution to the task planning instance: just have the helper do the length $T$ tasks and have us handle the other tasks in groups of 3 (each with length exactly equal to $T$).

Conversely, in any solution with no idle time, the helper cannot do any task of length less than $T$. If we start the helper on some task with length less than $T$ (i.e., some length $T/4< x_i< T/2$), we must find tasks to do ourselves with length exactly equal to $x_i$. However, no task other than $i$ itself has length $x_i$ (since all the integers $x_i$ are distinct) and for any two integers $x_j,x_k$, $x_j+x_k > T/2 > x_i$.

Thus, in any solution with no idle time, all the tasks done by the helper are of length $T$. The tasks we do ourselves during each task done by the helper must then form a solution to the 3-Partition instance.

Heuristic/approximation

Clearly the idle time cannot be approximated (since it is already hard to decide whether it is non-zero). There is however an EPTAS for the makespan.

Consider the algorithm that always assigns the longest job to the helper, and then fills out the schedule of the master by considering jobs in order of decreasing length and assigning each job that still fits (so that the length of master's schedule does not exceed that of the helper). Repeat this process with the remaining jobs untill all are scheduled. We call a single job done by the helper together with a set of jobs done by the master a "round".

This yields a solution with idle time of at most $L_\textrm{max}$ where $L_\textrm{max}$ denotes the length of the longest job. To see this, note that if during a round the master is idle for $\epsilon$ units of time, $L_\textrm{max}$ decreases (in the set of remaining jobs) by at least $\epsilon$: if there was a job longer than $L_\textrm{max}-\epsilon$ the master would have done that job and obtained a shorter idle time.

Suppose that the sum of all job lengths is $1$ and let $\epsilon < 1$. If $L_\textrm{max}\leq \epsilon$, the above procedure returns a $1+2\epsilon$-approximation (since the optimal solution has makespan $\geq 1/2$). Otherwise, consider the jobs with length $\geq \epsilon$ of which there are at most $1/{\epsilon}$ (long jobs). Consider also the jobs with $\epsilon <$ length $\geq \epsilon^2$ of which there are at most $1/{\epsilon^2}$ (medium jobs). The remaining jobs (with length $<\epsilon^2$) are called short.

We now, by brute force, enumerate all schedules with the following properties: all long jobs are scheduled, and possibly some medium jobs are scheduled and every round contains at least one long job. For each such schedule, we greedily fill any idle time the master may have with short jobs (so that the master does not work longer than the helper in any round). This is the first phase schdule. We then schedule the remaining short/medium jobs according to the previous greedy algorithm. This is the second phase schedule.

The idle time in the second phase is at most $\epsilon$ (since $L_\textrm{max}< \epsilon$). We now need to bound the additional idle time (over that in an optimal solution) in the first phase.

Take an optimal schedule. If the helper does a short job while the master does a long one, swap the jobs done by the helper and the master -- this does not change the makespan. Delete all short jobs from the schedule and all rounds containing only short/medium jobs. Assume the solution obtained by our approximation algorithm is based on this (modified) schedule, which will be part of the brute force enumeration (so our approximate solution will be at least as good as one obtained from this schedule).

If there are no short jobs in the second phase, then it is easy: We know that the medium jobs scheduled in the second phase do not need to be scheduled together with any long job in an optimal solution. In an optimal case they would be scheduled with at most zero idle time, and the greedy algorithm adds at most $2\epsilon$ extra idle time. We also have not increased the makespan of the brute-force schedule, so it must be optimal.

If there are any short jobs in the second phase, the first phase has at most $1/\epsilon$ rounds (because every round contains a long job) and no phase has more than $\epsilon^2$ idle time for the master (since otherwise we could have scheduled some of the remaining short jobs). Thus the total idle time for the master is at most $\epsilon$. In rounds were the helper has idle time, note that this round is unmodified from the original optimal schedule (since the master would not start a new job if the helper was idle). Thus, the additional idle time, over that of an optimal schedule, is at most $\epsilon$ (from rounds in which the master is idle; the rounds in which the helper is idle do not contribute any additional time).

An interesting question is what happens if the master is impatient and always starts a new job instead of having the option to wait for the helper to finish.

$\endgroup$
10
  • $\begingroup$ Also, suppose we introduce edge weights. The problem is now at least as hard as $3$-Partition. Do you now about any similar reductions? $\endgroup$ – gks Feb 1 at 9:51
  • $\begingroup$ @fda The edge weigths make no difference. In a reduction, we can just set them to 0 (or a very small value so they're inconsequential). The approximation question is interesting; I will think about it. $\endgroup$ – Tom van der Zanden Feb 1 at 10:07
  • $\begingroup$ @fda (I think) I found an approximation scheme. $\endgroup$ – Tom van der Zanden Feb 1 at 14:41
  • $\begingroup$ Thank you. One last question that I don't quite understand: Why are we allowed to ignore edge weights without losing generality? $\endgroup$ – gks Feb 1 at 17:07
  • 1
    $\begingroup$ @fda No, your comment on edge weights was referring to "reductions". Of course the approximation algorithm does not work for the edge weighted case; it doesn't take into account the edge weights at all so how could it? The edge weighted case cannot be approximated at all because TSP cannot be approximated. $\endgroup$ – Tom van der Zanden Feb 1 at 18:29

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.