Many polynomial-time solvable combinatorial optimization problems become NP-hard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximum-weight matching and maximum-weight matroid intersection with one additional budget constraint. We present the first polynomial-time approximation schemes for these problems. Similarly to other approaches for related problems, our schemes compute two solutions to the Lagrangian relaxation of the problem and patch them together to obtain a near-optimal solution. However, due to the richer combinatorial structure of the problems considered here, standard patching techniques do not apply. To circumvent this problem, we crucially exploit the adjacency relations on the solution polytope and, surprisingly, the solution to an old combinatorial puzzle. © 2008 Springer-Verlag Berlin Heidelberg.

Berger, A., Bonifaci, V., Grandoni, F., & Schafer, G. (2008). Budgeted matching and budgeted matroid intersection via the gasoline puzzle. In Proc. 13th Conf. on Integer Programming and Combinatorial Optimization (pp.273-287). Berlin : Springer [10.1007/978-3-540-68891-4_19].

Budgeted matching and budgeted matroid intersection via the gasoline puzzle

Bonifaci V.;
2008

Abstract

Many polynomial-time solvable combinatorial optimization problems become NP-hard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximum-weight matching and maximum-weight matroid intersection with one additional budget constraint. We present the first polynomial-time approximation schemes for these problems. Similarly to other approaches for related problems, our schemes compute two solutions to the Lagrangian relaxation of the problem and patch them together to obtain a near-optimal solution. However, due to the richer combinatorial structure of the problems considered here, standard patching techniques do not apply. To circumvent this problem, we crucially exploit the adjacency relations on the solution polytope and, surprisingly, the solution to an old combinatorial puzzle. © 2008 Springer-Verlag Berlin Heidelberg.
978-3-540-68886-0
Berger, A., Bonifaci, V., Grandoni, F., & Schafer, G. (2008). Budgeted matching and budgeted matroid intersection via the gasoline puzzle. In Proc. 13th Conf. on Integer Programming and Combinatorial Optimization (pp.273-287). Berlin : Springer [10.1007/978-3-540-68891-4_19].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/380496
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 14
social impact