日時 ： 2016年 4月21日(木) 15:00 ～ 16:00
場所 ： 東京大学 本郷キャンパス 工学部 14号館 5階 534号室
講演者： Alantha Newman (G-SCOP, Grenoble)
講演題目:
The Alternating Stock Size Problem and the Gasoline Puzzle
講演概要:
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 give a 2-approximation for this problem, based on rounding an LP
relaxation whose feasible solutions are convex combinations of
permutation matrices.
This is joint work with Heiko Roeglin (Universitaet Bonn) and Johanna
Seif (ENS Lyon).