The Alternating Stock Size Problem and the Gasoline Puzzle
Autor: | Alantha Newman, Heiko Röglin, Johanna Seif |
---|---|
Přispěvatelé: | Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Universität Bonn = University of Bonn, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science, Boston University [Boston] (BU), University of Bonn, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Perruet, Marie Josèphe, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon) |
Jazyk: | angličtina |
Rok vydání: | 2018 |
Předmět: |
FOS: Computer and information sciences
Doubly stochastic matrix [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0211 other engineering and technologies [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] 02 engineering and technology Combinatorics Mathematics (miscellaneous) 0502 economics and business Computer Science - Data Structures and Algorithms Prefix sum Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Stock (geology) ComputingMilieux_MISCELLANEOUS Mathematics 050210 logistics & transportation 021103 operations research 000 Computer science knowledge general works Rounding 05 social sciences Approximation algorithm Prefix Linear programming relaxation Computer Science Negative number |
Zdroj: | ACM Transactions on Algorithms ACM Transactions on Algorithms, 2018, 14 (2), pp.1-23. ⟨10.1145/3178539⟩ European Symposium on algorithms European Symposium on algorithms, Aug 2016, Aarhus, Denmark ACM Transactions on Algorithms, Association for Computing Machinery, 2018, 14 (2), pp.1-23. ⟨10.1145/3178539⟩ |
ISSN: | 1549-6325 |
DOI: | 10.1145/3178539⟩ |
Popis: | Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that (i) all prefix sums of the ordering are nonnegative and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. call this problem 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 numbers of positive and negative integers in the input set S are equal. The problem is the same as that shown earlier, 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. |
Databáze: | OpenAIRE |
Externí odkaz: |