On the Dial-a-Ride problem – 3

We present here a polynomial-time 2-approximation algorithm given by Charikar and Raghavachari [CR 2001] for the Capacitated Preemptive version of Dial-a-Ride on trees. For ease of visualization, we consider rooted trees, though the algorithm works as such for any tree.

The items are assumed to be located on the leaves of the tree, T. Consider a demand pair \{s_i, t_i\}. We will call the least common ancestor of s_i and t_i (the least-depth vertex in the unique path between s_i and t_i) as the turning point for that demand pair. Given the m demand pairs, all turning points can be easily computed in polynomial time. The algorithm that follows makes use of these pre-computed turning points.

The algorithm modifies the usual depth-first search, and runs two modified traversals in sequence. In the first traversal, called the upsweep, all items are shifted upwards from their sources to their respective turning points. In the second traversal, called the downsweep, the items are shifted downwards to their respective destinations.

Consider any edge e.

  • In the upsweep phase, the algorithm recursively explores the sub-tree rooted at e at the end of which all items that must necessarily pass upwards through e are shifted to the lower end point of e. The total number of such items is flow_u(e). The items are then shifted upwards across e. Clearly, edge e is traversed 2 max \{ 1, \lceil \frac{flow_u(e)}{k} \rceil \} times.
  • In the downsweep phase, items that need to pass downwards across e are shifted to the upper end point of e before the subtree rooted at e is recursively explored. Again, it is clear that e is traversed 2 max \{1, \lceil \frac{flow_d(e)} {k} \rceil \} times in the downsweep.

Notes:

  • Preemption is used in carrying items across edge e in the above description. The vehicle travels back and forth across e carrying items to the other end point.
  • Clearly, the algorithm runs in polynomial time.
  • This is a 2-approximation algorithm. This is obtained directly from the Steiner tree, and the flow lower bounds.

References:

  • [CR 2001] M. Charikar, B. Raghavachari: The Finite Capacity Dial-a-Ride Problem, 2001.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: