Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D1
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The Alternating Stock Size Problem and the Gasoline Puzzle
Speaker:Alantha Newman
coming from:CNRS-Université Grenoble Alpes
Speakers Bio:
Event Type:AG1 Advanced Mini-Course
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Saturday, 16 January 2016
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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 Röglin (Universität Bonn) and Johanna Seif (ENS Lyon).

Contact
Name(s):Tobias Moemke
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Tobias Moemke, 06/14/2016 01:51 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Tobias Moemke, 06/14/2016 01:51 PM -- Created document.