## Abstract

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 language | English |
---|---|

Title of host publication | Gems of Combinatorial Optimization and Graph Algorithms |

Publisher | Springer International Publishing AG |

Pages | 49-57 |

Number of pages | 9 |

ISBN (Electronic) | 9783319249711 |

ISBN (Print) | 9783319249704 |

DOIs | |

Publication status | Published - 31 Jan 2016 |