Budgeted Maximum Graph Coverage (2002)
Sven Oliver Krumke, Madhav V. Marathe, Diana Poensgen, S. S. Ravi
An instance of the maximum coverage problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total...
Multiple Hotlink Assignment (2002)
Sven Fuhrmann, Sven Oliver Krumke, Hans-christoph Wirth
The input for the hotlink assignment problem consists of a node weighted directed acyclic graph with a designated root node r. The goal is to minimize the weighted shortest path length rooted at r by...
On the Approximability of Location and Network Design Problems (1998)
Dissertation Zur Erlangung, Sven Oliver Krumke
This thesis investigates the approximability of several NP-hard location and network design problems. We present polynomial time approximation algorithms with a performance guarantee on the...