IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v22y2019i1d10.1007_s10951-018-0569-x.html
   My bibliography  Save this article

A polynomial-time approximation scheme for the airplane refueling problem

Author

Listed:
  • Iftah Gamzu

    (Amazon Research)

  • Danny Segev

    (University of Haifa)

Abstract

We consider the airplane refueling problem that was introduced by Gamow and Stern in their classical book Puzzle-Math (1958). In this setting, we wish to deliver a bomb the farthest possible distance, being much greater than the range of any individual airplane at our disposal. For this purpose, the only feasible option is to better utilize our fleet via mid-air refueling. Starting with a fleet of airplanes that can instantaneously refuel one another and gradually drop out of formation, how would we design the best refueling policy, i.e., one that maximizes the distance traveled by the last remaining plane? Even though Gamow and Stern provided an elegant characterization of the optimal refueling policy for the special case of identical airplanes, the general problem with arbitrary tank volumes and consumption rates has remained widely open, as pointed out by Woeginger (Albers et al., Dagstuhl seminar proceedings 10071, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2010). To our knowledge, other than a logarithmic approximation, which can be attributed to folklore, improved performance guarantees have not been obtained to date. In this paper, we propose a polynomial-time approximation scheme for the airplane refueling problem in its utmost generality. Our approach employs widely-known techniques related to geometric rounding, time stretching, guessing arguments, and timeline partitions. These are augmented by additional insight and ideas, that enable us to devise reductions to well-structured instances of generalized assignment and to exploit LP-rounding algorithms for the latter problem. We complement this result by presenting a fast and easy-to-implement algorithm that attains a constant factor approximation for the optimal refueling policy.

Suggested Citation

  • Iftah Gamzu & Danny Segev, 2019. "A polynomial-time approximation scheme for the airplane refueling problem," Journal of Scheduling, Springer, vol. 22(1), pages 119-135, February.
    • Handle: RePEc:spr:jsched:v:22:y:2019:i:1:d:10.1007_s10951-018-0569-x
    DOI: 10.1007/s10951-018-0569-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-018-0569-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-018-0569-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Thomson, William, 2011. "Chapter Twenty-One - Fair Allocation Rules," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 21, pages 393-506, Elsevier.
    2. Moran Feldman & Joseph (Seffi) Naor, 2017. "Non-preemptive buffer management for latency sensitive packets," Journal of Scheduling, Springer, vol. 20(4), pages 337-353, August.
    3. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2011. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 2, number 2.
    4. Julia Chuzhoy & Rafail Ostrovsky & Yuval Rabani, 2006. "Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 730-738, November.
    5. Lisa Fleischer & Michel X. Goemans & Vahab S. Mirrokni & Maxim Sviridenko, 2011. "Tight Approximation Algorithms for Maximum Separable Assignment Problems," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 416-431, August.
    6. Leslie A. Hall & Andreas S. Schulz & David B. Shmoys & Joel Wein, 1997. "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 513-544, August.
    7. José R. Correa & Martin Skutella & José Verschae, 2012. "The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 379-398, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bergantiños, Gustavo & Moreno-Ternero, Juan D., 2022. "Monotonicity in sharing the revenues from broadcasting sports leagues," European Journal of Operational Research, Elsevier, vol. 297(1), pages 338-346.
    2. Fleurbaey, Marc & Maniquet, François, 2017. "Fairness and well-being measurement," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 119-126.
    3. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2012. "A unifying framework for the problem of adjudicating conflicting claims," Journal of Mathematical Economics, Elsevier, vol. 48(2), pages 107-114.
    4. Sylvain Ferrières, 2017. "Nullified equal loss property and equal division values," Theory and Decision, Springer, vol. 83(3), pages 385-406, October.
    5. Moreno-Ternero, Juan D. & Roemer, John E., 2012. "A common ground for resource and welfare egalitarianism," Games and Economic Behavior, Elsevier, vol. 75(2), pages 832-841.
    6. Erlanson, Albin & Flores-Szwagrzak, Karol, 2015. "Strategy-proof assignment of multiple resources," Journal of Economic Theory, Elsevier, vol. 159(PA), pages 137-162.
    7. Chambers, Christopher P. & Moreno-Ternero, Juan D., 2021. "Bilateral redistribution," Journal of Mathematical Economics, Elsevier, vol. 96(C).
    8. Piacquadio, Paolo G., 2020. "The ethics of intergenerational risk," Journal of Economic Theory, Elsevier, vol. 186(C).
    9. Tanguy Isaac & Paolo Piacquadio, 2015. "Equity and efficiency in an overlapping generation model," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(3), pages 549-565, March.
    10. T. Hayashi & R. Jain & V. Korpela & M. Lombardi, 2023. "Behavioral strong implementation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(4), pages 1257-1287, November.
    11. Kranich, Laurence, 2020. "Resource-envy-free and efficient allocations: A new solution for production economies with dedicated factors," Journal of Mathematical Economics, Elsevier, vol. 89(C), pages 1-7.
    12. Cho, Wonki Jo, 2022. "How to add apples and oranges: Aggregating performances of different nature," Games and Economic Behavior, Elsevier, vol. 131(C), pages 222-244.
    13. Korpela, Ville, 2018. "Procedurally fair implementation under complete information," Journal of Mathematical Economics, Elsevier, vol. 77(C), pages 25-31.
    14. Piacquadio, Paolo G., 2014. "Intergenerational egalitarianism," Journal of Economic Theory, Elsevier, vol. 153(C), pages 117-127.
    15. Susumu Cato & Adrien Lutz, 2018. "Kenneth Arrow, moral obligations, and public policies," Working Papers halshs-01973898, HAL.
    16. Cornilly, Dries & Puccetti, Giovanni & Rüschendorf, Ludger & Vanduffel, Steven, 2022. "Fair allocation of indivisible goods with minimum inequality or minimum envy," European Journal of Operational Research, Elsevier, vol. 297(2), pages 741-752.
    17. Moreno-Ternero, Juan D. & Roemer, John E., 2012. "A common ground for resource and welfare egalitarianism," Games and Economic Behavior, Elsevier, vol. 75(2), pages 832-841.
    18. Heo, Eun Jeong, 2014. "Probabilistic assignment problem with multi-unit demands: A generalization of the serial rule and its characterization," Journal of Mathematical Economics, Elsevier, vol. 54(C), pages 40-47.
    19. Takuma Wakayama, 2017. "Bribe-proofness for single-peaked preferences: characterizations and maximality-of-domains results," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(2), pages 357-385, August.
    20. Leo Katz & Alvaro Sandroni, 2020. "Limits on power and rationality," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 507-521, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:22:y:2019:i:1:d:10.1007_s10951-018-0569-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.