Given one single-seat bicycle, n people with known walking and biking speeds, and a track of length d miles, devise a schedule that minimizes the arrival time of the last person at the finish line. Note that an optimal schedule might require biking backwards.
Overheads in postscript format
The following four animations illustrate some possible schedules for n = 3 and d = 10, where the first two people have walking speed 2 miles/hour and biking speed 12 miles/hour, and the third person has walking speed 4 miles/hour and biking speed 16 miles/hour.
For the two ε-optimal schedules, we must add the time necessary to get from the starting line to the initial positions and from the final positions to the finish line. The point is that, with enough stages, we can make this additional time less than any given ε > 0.
ε-Optimal Schedule Using Lemma 2 (ε = 8, One
Stage)
ε-Optimal Schedule Using Lemma 2 (ε = 4, Two
Stages)
Links to this page.
Return to my home page.