23 citations · 38 across the 14 of their papers we have counts for
5 papers · 1 filter
Travelling on Graphs with Small Highway Dimension
Yann Disser, Andreas Emil Feldmann, Max Klimm +1
We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] a…
Vehicle Routing with Subtours
Stephan Held, Jochen Könemann, Jens Vygen
When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items a…
Approximate Deadline-Scheduling with Precedence Constraints
Hossein Efsandiari, MohammadTaghi Hajiaghyi, Jochen Koenemann +3
We consider the classic problem of scheduling a set of n jobs non-preemptively on a single machine. Each job j has non-negative processing time, weight, and deadline, and a feasibl…
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree
Jochen Könemann, Sina Sadeghian, Laura Sanità
In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are given an undirected graph , non-negative costs and penalties for each .…
A Partition-Based Relaxation For Steiner Trees
Jochen Konemann, David Pritchard, Kunlun Tan
The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G…