MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

The Alternating Stock Size Problem and the Gasoline Puzzle

Alantha Newman
CNRS - Université Grenoble Alpes
AG1 Advanced Mini-Course
AG 1  
AG Audience
English

Date, Time and Location

Thursday, 16 June 2016
13:00
30 Minutes
E1 4
024
Saarbrücken

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 Lovasz, 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.

Joint work with Heiko Roeglin (Universitaet Bonn) and Johanna Seif
(ENS Lyon).

Contact

Tobias Moemke
--email hidden
passcode not visible
logged in users only

Uwe Brahm, 06/15/2016 11:40
Uwe Brahm, 06/15/2016 11:01 -- Created document.