2016-06-29
Budgeted matching via the gasoline puzzle
Publication
Publication
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 | |
|---|---|
| doi.org/10.1007/978-3-319-24971-1_5 | |
| Organisation | Networks and Optimization |
|
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 |
|
