**Uncertainty exploration**

*Meißner, Julie* (2018)

Combinatorial optimization captures a wide range of applications such as infrastructure design and scheduling of tasks. For a fixed number of possible new infrastructure connections or tasks to schedule, there are exponentially many infrastructure networks and schedules that can be created from them. Additionally, a major challenge is data uncertainty. If, for example, the construction cost of ...

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