This is part of a larger project that I am working on. It is not a contest problem.
Consider a complete graph $$$G = (V, E)$$$, where $$$V = {0, 1, 2, \ldots, n}$$$. The graph $$$G$$$ is a complete graph, so we can go from Vertex $$$i$$$ to Vertex $$$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 exactly $$$q_v > 0$$$ minutes, and we must complete all tasks. We start at Vertex $$$0$$$ and we have $$$q_0 = 0$$$.
Of course, it will take us exactly $$$\sum_{i = 1}^{n} q_i$$$ total time for us to complete all of the tasks on our own (it takes $$$0$$$ time to traverse edges). But now let's suppose that we have one helper. We can "dispatch" this helper at any one 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. The helper cannot move on its own; it must be picked up and dropped off by you. Essentially, we can "parallelize" this process to some extent.
Is there some sort of algorithm that allows one to find the best strategy that arises when we are allowed one helper?
I've already thought about greedy strategies (i.e, always drop the helper at the vertex that has the largest $$$q_i$$$, and go work on the quickest tasks available before coming back to pick up the helper), but there's no reason to believe that this is optimal. I thought that a DP on trees approach may help here, but I wanted to know what others thought.
Thank you.
If you're currently processing a vertex and the helper has just finished, can you put your current process on hold, grab the helper and then continue handling the same vertex?
Yes. I am not necessarily looking for a optimal solution though, so if you have some sort of approximation/heuristic, I would be fine with it.
Then the goal is basically to separate all vertexes into two sets $$$A$$$ and $$$B$$$, the first of which is processed directly and the second by a helper, minimizing $$$\max(\sum_{i \in A} q_i, \sum_{i \in B} q_i)$$$.
(That's because after splitting tasks like this, you can go to $$$B[1]$$$ and put helper there, then go to $$$A[1]$$$ and handle your task. If the task in $$$A[1]$$$ finishes before $$$B[1]$$$, you simply go to $$$A[2]$$$ and process it. After $$$B[1]$$$ finishes, you put your current task on hold, go to $$$B[2]$$$, put the helper there and return to your task.)
This task is equivalent to finding set $$$A$$$ such that $$$\sum_{i \in A} q_i \le \frac{1}{2} \sum_{i = 1}^n q_i$$$ and $$$\sum_{i \in A} q_i$$$ is maximized. Thus your task is reduceable to the classic knapsack problem.
Do I understand correctly that the graph never actually comes into play and we just have $$$n$$$ independent tasks? It seems so but now I'm puzzled as to why you introduced the graph, so I'm assuming I have misunderstood something.
It takes 0 time to traverse the edges and any node can visit any other node so I suppose you're right.
If the graph formed is an undirected weighted tree, is there some sort of tree dp solution or something?
For a simple tree
1--2 2--3 3--4 ... (n-1)--nwith zero-weight edges this problem is equivalent to knapsack. So, at least, there's no polynomial solution. I highly doubt there's a practically efficient solution on a tree.