Loading Events

« All Events

  • This event has passed.

ALOP-Colloquium with Sven Krumke

9. May 2016 / 16:00 - 18:00

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.


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.


9. May 2016
16:00 - 18:00
Event Category:


Research Training Group ALOP at Trier University


Trier University – E-Building – HS 9
Universität Trier Gebäude E
Trier, Rhineland-Palatinate 54296 Germany
+ Google Map