A polynomial-time approximation scheme for the airplane refueling problem

DOI10.1007/S10951-018-0569-XMaRDI QIDQ2327962zbMATH OpenOpenAlexWikidataFDO

Authors Iftah Gamzu, Danny Segev

Publication date 8 October 2019

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.06353

zbMATH Keywords

approximation algorithmsgeneralized assignmentPTASscheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Abstract: 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.

Recommendations

• A fast exact algorithm for airplane refueling problem
• The aircraft routing problem with refueling
• An efficient approximation algorithm for aircraft arrival sequencing and scheduling problem
• A linear-time algorithm for finding optimal vehicle refueling policies
• An efficient polynomial-time approximation scheme for the joint replenishment problem
• An iterative graph expansion approach for the scheduling and routing of airplanes
• Stochastic Airline Fleet Assignment is PSPACE-complete
• Integrated airline schedule design and fleet assignment: polyhedral analysis and Benders' decomposition approach
• The aircraft runway scheduling problem: a survey
• Computing aviation sparing policies: solving a large nonlinear integer program

Cites work

• A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
• A new approach to online scheduling: approximating the optimal competitive ratio
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• An approximation algorithm for the generalized assignment problem
• An efficient approximation for the generalized assignment problem
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Dual techniques for scheduling on a machine with varying speed
• How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions
• scientific article; zbMATH DE number 3136641 (Why is no real title available?)
• scientific article; zbMATH DE number 5764852 (Why is no real title available?)
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Non-preemptive buffer management for latency sensitive packets
• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Sum and Product in Dynamic Epistemic Logic
• The geometry of scheduling
• The power of preemption on unrelated machines and applications to scheduling orders
• The probabilistic method
• The Pure Theory of Elevators
• The submodular welfare problem with demand queries
• Tight approximation algorithms for maximum separable assignment problems

Cited in

(7)

• Refueling strategies to maximize the operational range of a nonidentical vehicle fleet
• Feeder routing for air-to-air refueling operations
• A fast exact algorithm for airplane refueling problem
• A novel MILP model for \(N\)-vehicle exploration problem
• For the airplane refueling problem local precedence implies global precedence
• Primal dual algorithms for the vehicle refueling problem
• Approximation Algorithms for Generalized Path Scheduling

This page was built for publication: A polynomial-time approximation scheme for the airplane refueling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2327962)