# Proving that no deterministic algorithm can be better than a 3-approximation

There are three popular beach resorts, A, B, and C, which reside on a line:

                    A-----(1km)-----B-----(1km)------C.


The distances between the resorts is 1km. John owns an ice-cream truck located in beach resort A and another located in beach resort C. Two busses full of ice-cream-craving children will arrive at the beach resorts (A, B, and C) tomorrow, but John does not know for which resort each bus is headed and when each bus will arrive (the busses can arrive at different times). He plans to dispatch an ice-cream truck from its current location to a beach resort as soon as a bus arrives at that resort. Each truck can only serve a single beach resort, that is, once a truck is dispatched to a beach resort it must remain there all day. John wants to design an algorithm that minimizes the sum of distances his trucks traverse in order to reach the busses’ locations.

Show that for every deterministic algorithm ALG, there is some scenario (i.e., schedule and locations of bus arrivals) in which the total distance Jonh’s trucks traverse under ALG is 3OPT, where OPT is the value of the optimal solution in that scenario.

-
What have you tried? Do you expect us to solve your homework for you? – Yuval Filmus Dec 3 '12 at 0:18
@AJed I hear you, but please maintain a friendly tone nonetheless. – Raphael Dec 3 '12 at 8:08