Source author record

Sven O. Krumke

Sven O. Krumke appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory Discrete Mathematics math.OC

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

On Reward-Penalty-Selection Games

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 sets, and a set of penalty sets, one tries to find a subset of elements such that as many reward sets as possible are covered, i.e. all elements are contained in the subset, and at the same time as few penalty sets as possible are hit, i.e. the intersection of the subset with the penalty set is non-empty. In this paper we define a cooperative game based on the RPSP where the elements of the RPSP are the players. We prove structural results and show that RPS games are convex, superadditive and totally balanced. Furthermore, the Shapley value can be computed in polynomial time. In addition to that, we provide a characterization of the core elements as a feasible flow in a network graph depending on the instance of the underlying RPSP. By using this characterization, a core element can be computed efficiently.

preprint2016arXiv

A Generalized Approximation Framework for Fractional Network Flow and Packing Problems

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 approximation algorithms for problems of the form $\max\{c^T x : Ax \leq b, x \in C \}$, where the matrix $A$ contains no negative entries and $C$ is a cone that is generated by a finite set $S$ of non-negative vectors. While the cone is allowed to require an exponential-sized representation, we assume that we can access it via one of three types of oracles. For each of these oracles, we present positive results for the approximability of the packing problem. In contrast to other frameworks, the presented one allows the use of arbitrary linear objective functions and can be applied to a large class of packing problems without much effort. In particular, our framework instantly allows to derive fast and simple fully polynomial-time approximation algorithms (FPTASs) for a large set of network flow problems, such as budget-constrained versions of traditional network flows, multicommodity flows, or generalized flows. Some of these FPTASs represent the first ones of their kind, while others match existing results but offer a much simpler proof.

preprint2016arXiv

On the Complexity and Approximability of Budget-Constrained Minimum Cost Flows

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 second kind of costs associated with each edge, whose total value in a feasible flow is constrained by a given budget B. This problem can, e.g., be seen as the application of the ε-constraint method to the bicriteria minimum cost flow problem. We show that we can solve the problem exactly in weakly polynomial time $O(\log M \cdot MCF(m,n,C,U))$, where C, U, and M are upper bounds on the largest absolute cost, largest capacity, and largest absolute value of any number occuring in the input, respectively, and MCF(m,n,C,U) denotes the complexity of finding a traditional minimum cost flow. Moreover, we present two fully polynomial-time approximation schemes for the problem on general graphs and one with an improved running-time for the problem on acyclic graphs.

preprint2015arXiv

ReOpt: an Algorithm with a Quality Guaranty for Solving the Static Relocation Problem

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 satisfactory way, the stations have to keep a good ratio between the numbers of free places and cars in each station. This leads to the problem of relocating cars between stations, which can be modeled within the framework of a metric task system. In this paper, we focus on the Static Relocation Problem, where the system has to be set into a certain state, outgoing from the current state. We present a combinatorial approach and provide approximation factors for several different situations.