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.
|Title of host publication||Gems of Combinatorial Optimization and Graph Algorithms|
|Publisher||Springer International Publishing AG|
|Number of pages||9|
|Publication status||Published - 31 Jan 2016|