The Alternating Stock Size Problem and the Gasoline Puzzle

Session : GTSS2-2 / GTSS2 : Heuristics and approximation algorithms for scheduling problems
Jeudi 11 février 15:00 - 16:40 Salle : CI2-04
Alantha Newman, Heiko Roeglin et Johanna Seif

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. refer 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" in which 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 Lovasz, in which we want to minimize the size of the gas tank necessary to go around the track. We give approximation algorithms for this problem as well, based on rounding LP relaxations whose feasible solutions are convex combinations of permutation matrices.

Mots clés : approximation algorithms, permutations, resource allocation