arXiv preprint ·
A Fast Greedy Algorithm with a 0.45 Approximation Guarantee for the Airplane Refueling Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study a natural greedy algorithm for the Airplane Refueling Problem (ARP), based on a well-known priority rule. We show that this algorithm achieves an approximation guarantee of $9/20$, noticeably improving the previously known $1/12$ guarantee for a fast algorithm. We also show that the same priority rule can be implemented in $O(n\log n)$ time and $O(n)$ space using a dynamic convex-hull data structure. These results provide a worst-case approximation guarantee for an existing greedy priority rule and establish an efficient implementation. In the real-RAM model, the running-time bound is independent of the magnitude of the processing times. The resulting method is also suitable as a fast primal routine inside more complex exact and approximation algorithms for large instances. These results narrow the gap between theoretically strong but complex approximation schemes and lightweight algorithms that can be used directly in computational pipelines. The algorithm combines a simple selection rule with a provable performance bound, making it a useful baseline for further algorithmic studies of ARP.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
Polynomial directed treewidth forces a large bramble with congestion two
A Quantum Analogue of the Covering Lemma: Limits of Exact Anonymous Computation
An ETH-based quasipolynomial lower bound for Dualization
Dynamic Conflict Clustering with Lightweight Learning and Strategic Repair for Distributed Constraint Satisfaction
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.