direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 49-2007

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle
Authors
Andre Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer
Publication
submitted
Classification
not available
Keywords
combinatorial optimization, approximation algorithms, matching, matroid intersection, polynomial-time approximation scheme
Abstract
Many polynomial-time solvable combinatorial optimization problems become NP-hard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximum-weight matching and maximum-weight matroid intersection with one additional budget constraint. We present the first poly-nomial-time approximation schemes for these problems.
Similarly to other approaches for related problems, our schemes compute two solutions to the Lagrangian relaxation of the problem and patch them together. However, due to the richer combinatorial structure of the problems considered here, standard patching techniques do not apply. To circumvent this problem, we crucially exploit the adjacency relations on the solution polytope and, somewhat surprisingly, the solution to an old combinatorial puzzle.
Source
Download as [PDF]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe