Budgeted matching via the gasoline puzzle

Guido Schäfer*

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review


We consider a natural generalization of the classical matching problem: In the budgeted matching problem we are given an undirected graph with edge weights, non-negative edge costs and a budget. The goal is to compute a matching of maximum weight such that its cost does not exceed the budget. This problem is weakly NP-hard. We present the first polynomial-time approximation scheme for this problem. Our scheme computes two solutions to the Lagrangian relaxation of the problem and patches them together to obtain a near-optimal solution. In our patching procedure we crucially exploit the adjacency relations of vertices of the matching polytope and the solution to an old combinatorial puzzle.

Original languageEnglish
Title of host publicationGems of Combinatorial Optimization and Graph Algorithms
PublisherSpringer International Publishing AG
Number of pages9
ISBN (Electronic)9783319249711
ISBN (Print)9783319249704
Publication statusPublished - 31 Jan 2016


Dive into the research topics of 'Budgeted matching via the gasoline puzzle'. Together they form a unique fingerprint.

Cite this