There are 3 popular beach resorts, A, B, and C, which reside on a line:
A-----(1km)-----B-----(1km)------C.
The distances between the resorts is 1k. 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.
