5 citations · 10 across the 9 of their papers we have counts for
17 papers
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
Allocating indivisible items among a set of agents is a frequently studied discrete optimization problem. In the setting considered in this work, the agents' preferences over the i…
Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
We consider the task of allocating indivisible items to agents, when the agents' preferences over the items are identical. The preferences are captured by means of a directed acycl…
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…
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…
Dispersing Obnoxious Facilities on Graphs by Rounding Distances
Tim A. Hartmann, Stefan Lendl
We continue the study of -dispersion, a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the i…
Allocation of Indivisible Items with Individual Preference Graphs
Nina Chiarelli, Clément Dallard, Andreas Darmann +5
This paper studies the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph. The vertices of each preference…
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…
An Investigation of the Recoverable Robust Assignment Problem
Dennis Fischer, Tim A. Hartmann, Stefan Lendl +1
We investigate the so-called recoverable robust assignment problem on balanced bipartite graphs with vertices, a mainstream problem in robust optimization: For two given linea…
Robust Combinatorial Optimization with Locally Budgeted Uncertainty
Marc Goerigk, Stefan Lendl
Budgeted uncertainty sets have been established as a major influence on uncertainty modeling for robust optimization problems. A drawback of such sets is that the budget constraint…
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…
Matroid Bases with Cardinality Constraints on the Intersection
Stefan Lendl, Britta Peis, Veerle Timmermans
Given two matroids and on a common ground set with base sets and $\mathcal{B…
Dispersing obnoxious facilities on a graph
Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl +1
We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal i…
On Streaming Algorithms for the Steiner Cycle and Path Cover Problem on Interval Graphs and Falling Platforms in Video Games
Ante Ćustić, Stefan Lendl
We introduce a simplified model for platform game levels with falling platforms based on interval graphs and show that solvability of such levels corresponds to finding Steiner cyc…
On sequences covering all rainbow -progressions
Leonardo Alese, Stefan Lendl, Paul Tabatabai
Let denote the smallest positive integer with the property that there exists an -colouring of such that for every -subset $R…
Combinatorial Optimization Problems with Interaction Costs: Complexity and Solvable Cases
Stefan Lendl, Ante Ćustić, Abraham P. Punnen
We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two giv…