FG Kombinatorische Optimierung und Graphenalgorithmen

2 Items

Recent Submissions
On linkages in polytope graphs

Werner, Axel ; Wotzlaw, Ronald F. (2011)

A graph is k-linked if any k disjoint vertex-pairs can be joined by k disjoint paths. We slightly improve a lower bound on the linkedness of polytopes. This results in exact values for the minimal linkedness of 7-, 10- and 13-dimensional polytopes.

How unsplittable-flow-covering helps scheduling with job-dependent cost functions

Höhn, Wiebke ; Mestre, Julián ; Wiese, Andreas (2017)

Generalizing many well-known and natural scheduling problems, scheduling with job-specific cost functions has gained a lot of attention recently. In this setting, each job incurs a cost depending on its completion time, given by a private cost function, and one seeks to schedule the jobs to minimize the total sum of these costs. The framework captures many important scheduling objectives such a...