FG Kombinatorische Optimierung und Graphenalgorithmen

6 Items

Recent Submissions
Flows over time and submodular function minimization

Schlöter, Miriam (2018)

Many parts of our daily routine that we expect to "just work" rely on certain optimization processes that most of the time take place in a network. Ranging from streets, railroads or power networks to the telecommunications network used by the Internet and the networks induced by social networks: the list of structures that can be modeled as a network goes on and on and optimization processes o...

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