The Alternating Stock Size Problem and the Gasoline Puzzle

Authors Alantha Newman, Heiko Röglin, Johanna Seif



PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.71.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Alantha Newman
Heiko Röglin
Johanna Seif

Cite AsGet BibTex

Alantha Newman, Heiko Röglin, and Johanna Seif. The Alternating Stock Size Problem and the Gasoline Puzzle. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.71

Abstract

Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefixes of the ordering are non-negative, and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. referred to this problem as the stock size problem and showed that it can be approximated to within 3/2. They also showed that an approximation ratio of 2 can be achieved via several simple algorithms. We consider a related problem, which we call the alternating stock size problem, where the number of positive and negative integers in the input set S are equal. The problem is the same as above, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple 2-approximations. We show that it can be approximated to within 1.79. Then we show that this problem is closely related to an optimization version of the gasoline puzzle due to Lovász, in which we want to minimize the size of the gas tank necessary to go around the track. We present a 2-approximation for this problem, using a natural linear programming relaxation whose feasible solutions are doubly stochastic matrices. Our novel rounding algorithm is based on a transformation that yields another doubly stochastic matrix with special properties, from which we can extract a suitable permutation.
Keywords
  • approximation algorithms
  • stock size problem
  • scheduling with non-renewable resources

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. H. M. Abdel-Wahab and T. Kameda. Scheduling to minimize maximum cumulative cost subject to series-parallel precedence constraints. Operations Research, 26(1):141-158, 1978. Google Scholar
  2. Wojciech Banaszczyk. The steinitz constant of the plane. Journal für die Reine und Angewandte Mathematik, 373:218-220, 1987. Google Scholar
  3. Imre Bárány. On the power of linear dependencies. In Building bridges, pages 31-45. Springer, 2008. Google Scholar
  4. Jacek Blazewicz, Jan Karel Lenstra, and AHG Rinnooy Kan. Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics, 5(1):11-24, 1983. Google Scholar
  5. Dirk Briskorn, Byung-Cheon Choi, Kangbok Lee, Joseph Leung, and Michael Pinedo. Complexity of single machine scheduling subject to nonnegative inventory constraints. European Journal of Operational Research, 207(2):605-619, 2010. Google Scholar
  6. J Carlier and AHG Rinnooy Kan. Scheduling subject to nonrenewable-resource constraints. Operations Research Letters, 1(2):52-55, 1982. Google Scholar
  7. V. S. Grinberg and S. V. Sevastyanov. The value of the Steinitz constant. Functional Analysis and its Applications, 14:56-57, 1980. Google Scholar
  8. Péter Györgyi and Tamás Kis. Approximation schemes for single machine scheduling with non-renewable resource constraints. Journal of Scheduling, 17(2):135-144, 2014. Google Scholar
  9. Péter Györgyi and Tamás Kis. Approximability of scheduling problems with resource consuming jobs. Annals of Operations Research, 235(1):319-336, 2015. Google Scholar
  10. Nick Harvey and Samira Samadi. Near-optimal herding. In COLT, pages 1165-1182, 2014. Google Scholar
  11. Hans Kellerer, Vladimir Kotov, Franz Rendl, and Gerhard J. Woeginger. The stock size problem. Operations Research, 46(3):S1-S12, 1998. Google Scholar
  12. L. Lovász. Combinatorial Problems and Exercises. North-Holland, 1979. Google Scholar
  13. Clyde L. Monma. Sequencing to minimize the maximum job cost. Operations Research, 28(4):942-951, 1980. Google Scholar
  14. Ehab Morsy and Erwin Pesch. Approximation algorithms for inventory constrained scheduling on a single machine. Journal of Scheduling, 18(6):645-653, 2015. Google Scholar
  15. Klaus Neumann and Christoph Schwindt. Project scheduling with inventory constraints. Mathematical Methods of Operations Research, 56(3):513-533, 2003. Google Scholar
  16. Alantha Newman, Heiko Röglin, and Johanna Seif. The alternating stock size problem and the gasoline puzzle. arXiv:1511.09259, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail