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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-24971-1_5
Schäfer, G. (2016). Budgeted matching via the gasoline puzzle. In Gems of Combinatorial Optimization and Graph Algorithms (pp. 49–57). doi:10.1007/978-3-319-24971-1_5