Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14377
For citation please use:
Main Title: Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle
Author(s): Berger, Andre
Bonifaci, Vincenzo
Grandoni, Fabrizio
Schäfer, Guido
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15604
http://dx.doi.org/10.14279/depositonce-14377
License: http://rightsstatements.org/vocab/InC/1.0/
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.
Subject(s): combinatorial optimization
approximation algorithms
matching
matroid intersection
polynomial-time approximation scheme
Issue Date: 2007
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2007, 49
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-049-2007.pdf
Format: Adobe PDF | Size: 98.44 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.