ALOP-Colloquium with Sven Krumke

On May 9, 2016 Sven Krumke from the Technische Universität Kaiserslautern will join the ALOP-Colloquium and present his recent work. At 15:45 there will be a coffee hour in E10.  The presentation will take place in HS10 at 16:15.

Abstract

We present a generalization of the fractional packing framework introduced by Garg and Koenemann (2007) that incorporates Megiddo’s (1979) parametric search technique: Given a polyhedral cone that is finitely generated by a (possibly exponential-size) set of non-negative vectors and given an oracle that returns a vector in this set with minimum cost with respect to a given cost vector, we obtain a fully polynomial-time approximation scheme for the problem of minimizing a linear cost function over the cone subject to a set of packing constraints. This general framework yields several applications for budget-constrained versions of well-known flow problems such as
– budget-constrained maximum flow
– budget-constrained minimum cost flow
– budget-constrained minimum cost generalized flow
– budget-constrained minimum cost flow in processing networks.
For all of these problems, we are able to derive strongly polynomial-time FPTAS using the generalized fractional packing framework.