1 Search Results for "Seif, Johanna"

Document

DOI: 10.4230/LIPIcs.ESA.2016.71

The Alternating Stock Size Problem and the Gasoline Puzzle

Authors: Alantha Newman, Heiko Röglin, and Johanna Seif

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{newman_et_al:LIPIcs.ESA.2016.71,
  author =	{Newman, Alantha and R\"{o}glin, Heiko and Seif, Johanna},
  title =	{{The Alternating Stock Size Problem and the Gasoline Puzzle}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{71:1--71:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.71},
  URN =		{urn:nbn:de:0030-drops-64134},
  doi =		{10.4230/LIPIcs.ESA.2016.71},
  annote =	{Keywords: approximation algorithms, stock size problem, scheduling with non-renewable resources}
}

Refine by Author
1 Newman, Alantha
1 Röglin, Heiko
1 Seif, Johanna

Refine by Classification

Refine by Keyword
1 approximation algorithms
1 scheduling with non-renewable resources
1 stock size problem

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Seif, Johanna"

The Alternating Stock Size Problem and the Gasoline Puzzle

Abstract

Cite as

Thanks for your feedback!

Could not send message