FG Kombinatorische Optimierung und Graphenalgorithmen

9 Items

Recent Submissions
On orthogonal symmetric chain decompositions

Däubel, Karl ; Jäger, Sven ; Mütze, Torsten ; Scheucher, Manfred (2019-09-27)

The n-cube is the poset obtained by ordering all subsets of {1,…,n} by inclusion, and it can be partitioned into (n⌊n/2⌋) chains, which is the minimum possible number. Two such decompositions of the n-cube are called orthogonal if any two chains of the decompositions share at most a single element. Shearer and Kleitman conjectured in 1979 that the n-cube has ⌊n/2⌋+1 pairwise orthogonal decompos...

Nash flows over time

Sering, Leon (2020)

Motivated by the dynamic traffic assignment problem and with the goal in mind to obtain a better understanding of the complex traffic dynamics, we consider a dynamic game in a flow over time model with deterministic queuing in this thesis. The dynamic equilibria, called Nash flows over time, in the base version of this model were introduced by Koch and Skutella in 2009 and they were already stu...

Some aspects of graph sparsification in theory and practice

Däubel, Karl (2020)

Many applications in transportation, telecommunication, logistics, biology or social networks, only to name a few examples, can be modelled by graphs. The size of graphs encountered in these applications is large, ranging from millions of vertices and edges in the European road network to billions of vertices and one hundred billion edges in the World-Wide Web graph. The order of magnitude of t...

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