  We study the airplane refueling problem which was introduced by the
physicists Gamow and Stern in their classical book Puzzle-Math (1958). Sticking
to the original story behind this problem, suppose we have to deliver a bomb in
some distant point of the globe, the distance being much greater than the range
of any individual airplane at our disposal. Therefore, the only feasible option
to carry out this mission is to better utilize our fleet via mid-air refueling.
Starting with several airplanes that can refuel one another, and gradually drop
out of the flight until the single plane carrying the bomb reaches the target,
how would you plan the refueling policy?
  The main contribution of Gamow and Stern was to provide a complete
characterization of the optimal refueling policy for the special case of
identical airplanes. In spite of their elegant and easy-to-analyze solution,
the computational complexity of the general airplane refueling problem, with
arbitrary tank volumes and consumption rates, has remained widely open ever
since, as recently pointed out by Woeginger (Open Problems in Scheduling,
Dagstuhl 2010, page 24). To our knowledge, other than a logarithmic
approximation, which can be attributed to folklore, it is not entirely obvious
even if constant-factor performance guarantees are within reach.
  In this paper, we propose a polynomial-time approximation scheme for the
airplane refueling problem in its utmost generality. Our approach builds on a
novel combination of ideas related to parametric pruning, efficient guessing
tricks, reductions to well-structured instances of generalized assignment, and
additional insight into how LP-rounding algorithms in this context actually
work. We complement this result by presenting a fast and easy-to-implement
algorithm that approximates the optimal refueling policy to within a constant
factor.

Data Structures and Algorithms