FG Kombinatorische Optimierung und Graphenalgorithmen

4 Items

Recent Submissions
Stable marriage and roommates problems with restricted edges: complexity and approximability

Cseh, Ágnes ; Manlove, David F. (2016-04-16)

In the Stable Marriage and Roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the comp...

Matchings with lower quotas: algorithms and complexity

Arulselvan, Ashwin ; Cseh, Ágnes ; Groß, Martin ; Manlove, David F. ; Matuschke, Jannik (2016-11-21)

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph G=(A∪˙P,E) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either u...

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...