7 papers
Maximum Covering Network Design on Graphs with Low Connectivity: Dynamic Programming and Block-Cut Trees
Felix Rauh, Jannik Matuschke, Hande Yaman
Planning accessible public services such as health care, emergency response, and schools often requires not only choosing where to open facilities but also improving the network th…
When to Identify Is to Control: On the Controllability of Combinatorial Optimization Problems
Max Klimm, Jannik Matuschke
Consider a finite ground set , a set of feasible solutions , and a class of objective functions defined on . We are interested in su…
Condorcet Dimension and Pareto Optimality for Matchings and Beyond
Telikepalli Kavitha, Jannik Matuschke, Ulrike Schmidt-Kraepelin
We study matching problems in which agents form one side of a bipartite graph and have preferences over objects on the other side. A central solution concept in this setting is pop…
Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction
Jannik Matuschke
We study the following fundamental network optimization problem known as Maximum Robust Flow (MRF): A planner determines a flow on --paths in a given capacitated network. The…
Simultaneous Network Design with Restricted Link Usage
Naonori Kakimura, Péter Madarasi, Jannik Matuschke +1
Given a digraph with two terminal vertices and as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to fin…
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
Umang Bhaskar, Katharina Eickhoff, Lennart Kauther +3
In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requi…