6
$\begingroup$

This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:

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?


As a summary, in the initial post, I asked for an approximation/heuristic that would allow me to minimize the total time spent completing all of the tasks with the assistance of a helper. Tom van der Zanden proposed an answer in which the longest job is always assigned to the helper, and they showed that this is an efficient polynomial-time approximation scheme for the makespan.

However, I now want to consider a slight variant of the problem. Most of the problem remains the same, but the following constraint is added: The helper cannot be dispatched at any node. Instead, there is a subset of vertices $S \subseteq V$ that is known to everyone at the start of problem, and the helper can only be dispatched at the vertices in this subset.

I looked at the extreme cases (i.e., $S = \emptyset$ and $S = V$). When $S = V$, the heuristic proposed in the previous post obviously works. When $S = \emptyset$, the total time taken is fixed since we cannot exercise the option to use a helper vehicle.

I was wondering whether there was an approximation scheme or heuristic that might be efficient in this general case.

$\endgroup$
3
  • $\begingroup$ Can you give a self-contained specification of the problem in this question, so we don't have to refer to the other question to understand the task you want to solve? $\endgroup$
    – D.W.
    Feb 10 at 22:35
  • $\begingroup$ You can not stop a task mid-way through to move the helper, then resume the task you are doing, right? $\endgroup$
    – orlp
    Feb 15 at 23:20
  • $\begingroup$ @orlp Yes, you cannot stop a task midway and resume the task. That is forbidden. One must spend $q_i$ uninterrupted minutes. $\endgroup$
    – user127619
    Feb 15 at 23:38

Your Answer

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