19 citations · 61 across the 20 of their papers we have counts for
20 papers
Almost Disjoint Paths and Separating by Forbidden Pairs
Oliver Bachtler, Tim Bergner, Sven O. Krumke
By Menger's theorem the maximum number of arc-disjoint paths from a vertex s to a vertex t in a directed graph equals the minumum number of arcs needed to disconnect s and t, i.e.,…
On Reward-Penalty-Selection Games
Niklas Gräf, Till Heller, Sven O. Krumke
The Reward-Penalty-Selection Problem (RPSP) can be seen as a combination of the Set Cover Problem (SCP) and the Hitting Set Problem (HSP). Given a set of elements, a set of reward…
The Reward-Penalty-Selection Problem
T. Heller, S. O. Krumke, K. -H. Küfer
The Set Cover Problem (SCP) and the Hitting Set Problem (HSP) are well-studied optimization problems. In this paper we introduce the Reward-Penalty-Selection Problem (RPSP) which c…
On the Connection between Individual Scaled Vickrey Payments and the Egalitarian Allocation
N. Gräf, T. Heller, S. O. Krumke
The Egalitarian Allocation (EA) is a well-known profit sharing method for cooperative games which attempts to distribute profit among participants in a most equal way while respect…
On the Bicriterion Maximum Flow Network Interdiction Problem
Luca E. Schäfer, Stefan Ruzika, Sven O. Krumke +1
This article focuses on a biobjective extension of the maximum flow network interdiction problem, where each arc in the network is associated with two capacity values. Two maximum…
Towards obtaining a 3-Decomposition from a perfect Matching
Oliver Bachtler, Sven O. Krumke
A decomposition of a graph is a set of subgraphs whose edges partition those of . The 3-decomposition conjecture posed by Hoffmann-Ostenhof in 2011 states that every connected c…
Robust Single Machine Makespan Scheduling with Release Date Uncertainty
Oliver Bachtler, Sven O. Krumke, Huy Minh Le
This paper addresses the robust single machine makespan scheduling with uncertain release dates of the jobs. The release dates take values within know intervals. We use the concept…
Scheduling a Proportionate Flow Shop of Batching Machines
Christoph Hertrich, Christian Weiß, Heiner Ackermann +2
In this paper we study a proportionate flow shop of batching machines with release dates and a fixed number of machines. The scheduling problem has so far barely receive…
Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines
Christoph Hertrich, Christian Weiß, Heiner Ackermann +2
This paper is the first to consider online algorithms to schedule a proportionate flexible flow shop of batching machines (PFFB). The scheduling model is motivated by manufacturing…
On the Mixed Connectivity Conjecture of Beineke and Harary
Sebastian S. Johann, Sven O. Krumke, Manuel Streicher
The conjecture of Beineke and Harary states that for any two vertices which can be separated by vertices and edges for but neither by vertices and edges…
Robust Multicovers with Budgeted Uncertainty
Sven O. Krumke, Eva Schmidt, Manuel Streicher
The Min--Multiset Multicover problem presented in this paper is a special version of the Multiset Multicover problem. For a fixed positive integer , we are given a finite gro…
Simultaneously Dominating all Spanning Trees of a Graph
Sebastian S. Johann, Sven O. Krumke, Manuel Streicher
We investigate the problem of simultaneously dominating all spanning trees of a given graph. We prove that on 2-connected graphs, a subset of the vertices dominates all spanning tr…
An FPTAS for the Knapsack Problem with Parametric Weights
Michael Holzhauser, Sven O. Krumke
In this paper, we investigate the parametric weight knapsack problem, in which the item weights are affine functions of the form for $i \in \{1,\ldots,n…
An FPTAS for the parametric knapsack problem
Michael Holzhauser, Sven O. Krumke
In this paper, we investigate the parametric knapsack problem, in which the item profits are affine functions depending on a real-valued parameter. The aim is to provide a solution…
Minimum Cycle Decomposition: A Constructive Characterization for Graphs of Treewidth Two with Node Degrees Two and Four
Irene Heinrich, Sven O. Krumke
Substantial efforts have been made to compute or estimate the minimum number of cycles needed to partition the edges of an Eulerian graph. We give an equivalent characteriza…
A Generalized Approximation Framework for Fractional Network Flow and Packing Problems
Michael Holzhauser, Sven O. Krumke
We generalize the fractional packing framework of Garg and Koenemann to the case of linear fractional packing problems over polyhedral cones. More precisely, we provide approximati…
On the Complexity and Approximability of Budget-Constrained Minimum Cost Flows
Michael Holzhauser, Sven O. Krumke, Clemens Thielen
We investigate the complexity and approximability of the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a secon…
A Network Simplex Method for the Budget-Constrained Minimum Cost Flow Problem
Michael Holzhauser, Sven O. Krumke, Clemens Thielen
We present a specialized network simplex algorithm for the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a sec…
ReOpt: an Algorithm with a Quality Guaranty for Solving the Static Relocation Problem
Sahar Bsaybes, Sven O. Krumke, Alain Quilliot +2
In a carsharing system, a fleet of cars is distributed at stations in an urban area, customers can take and return cars at any time and station. For operating such a system in a sa…
Complexity of Strong Implementability
Clemens Thielen, Sven O. Krumke
We consider the question of implementability of a social choice function in a classical setting where the preferences of finitely many selfish individuals with private information…