1 citations · 3 across the 12 of their papers we have counts for
16 papers
The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
Marc Goerigk, Dorothee Henke, Lasse Wulf
A standard type of uncertainty set in robust optimization is budgeted uncertainty, where an interval of possible values for each parameter is given and the total deviation from the…
On Finding -th Smallest Perfect Matchings
Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner +1
Given an undirected weighted graph and an integer , Exact-Weight Perfect Matching (EWPM) is the problem of finding a perfect matching of weight exactly in . In this p…
Fréchet Distance in Unweighted Planar Graphs
Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg +1
The Fréchet distance is a distance measure between trajectories in or walks in a graph . Given constant-time shortest path queries, the Discrete Fréchet distance $D_…
Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
Lasse Wulf
The diameter of a polytope is a fundamental geometric parameter that plays a crucial role in understanding the efficiency of the simplex method. Despite its central nature, the com…
On the Exact Matching Problem in Dense Graphs
Nicolas El Maalouly, Sebastian Haslebacher, Lasse Wulf
In the Exact Matching problem, we are given a graph whose edges are colored red or blue and the task is to decide for a given integer k, if there is a perfect matching with exactly…
An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs
Anita Dürr, Nicolas El Maalouly, Lasse Wulf
In 1982 Papadimitriou and Yannakakis introduced the Exact Matching problem, in which given a red and blue edge-colored graph and an integer one has to decide whether there…
A linear time algorithm for linearizing quadratic and higher-order shortest path problems
Eranda Çela, Bettina Klinz, Stefan Lendl +2
An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same…
Exact Matching and the Top-k Perfect Matching Problem
Nicolas El Maalouly, Lasse Wulf
The aim of this note is to provide a reduction of the Exact Matching problem to the Top- Perfect Matching Problem. Together with earlier work by El Maalouly, this shows that the…
On the Multi-Robber Damage Number
Miloš Stojaković, Lasse Wulf
We study a variant of the Cops and Robbers game on graphs in which the robbers damage the visited vertices, aiming to maximize the number of damaged vertices. For that game with on…
On the Complexity of Robust Multi-Stage Problems in the Polynomial Hierarchy
Marc Goerigk, Stefan Lendl, Lasse Wulf
We study the computational complexity of multi-stage robust optimization problems. Such problems are formulated with alternating min/max quantifiers and therefore naturally fall in…
Exact Matching: Correct Parity and FPT Parameterized by Independence Number
Nicolas {El Maalouly}, Raphael Steiner, Lasse Wulf
Given an integer and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly…
On the Recoverable Traveling Salesman Problem
Marc Goerigk, Stefan Lendl, Lasse Wulf
In this paper we consider the Recoverable Traveling Salesman Problem (TSP). Here the task is to find two tours simultaneously, such that the intersection between the tours is at le…
Assistance and Interdiction Problems on Interval Graphs
Hung P. Hoang, Stefan Lendl, Lasse Wulf
We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of origina…
Two-Stage Robust Optimization Problems with Two-Stage Uncertainty
Marc Goerigk, Stefan Lendl, Lasse Wulf
We consider two-stage robust optimization problems, which can be seen as games between a decision maker and an adversary. After the decision maker fixes part of the solution, the a…
Recoverable Robust Representatives Selection Problems with Discrete Budgeted Uncertainty
Marc Goerigk, Stefan Lendl, Lasse Wulf
Recoverable robust optimization is a multi-stage approach, where it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We analyze this appr…
A Greedy Heuristic for Crossing-Angle Maximization
Almut Demel, Dominik Dürrschnabel, Tamara Mchedlidze +2
The crossing angle of a straight-line drawing of a graph is the smallest angle between two crossing edges in . Deciding whether a graph has a straight-line dr…