Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle (Articolo in rivista)

Type

• Prodotto della ricerca (Classe)
• Articolo in rivista (Classe)

Label

• Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle (Articolo in rivista) (literal)

Anno

• 2011-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1007/s10107-009-0307-4 (literal)

Alternative label

• Berger, A.; Bonifaci, V.; Grandoni, F.; Schaefer, G. (2011)
  Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle
  in Mathematical programming
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• Berger, A.; Bonifaci, V.; Grandoni, F.; Schaefer, G. (literal)

Pagina inizio

• 355 (literal)

Pagina fine

• 372 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 128 (literal)

Rivista

• Mathematical programming (Rivista)

Note

• ISI Web of Science (WOS) (literal)
• Scopu (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• Maastricht University, the Netherlands University of L'Aquila and Sapienza University of Rome, Italy University of Rome Tor Vergata, Italy VU University and CWI, the Netherlands (literal)

Titolo

• Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle (literal)

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. (literal)

Prodotto di

• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)
• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)

Autore CNR

• VINCENZO BONIFACI (Unità di personale interno)

Incoming links:

Prodotto

• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)
• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)

Autore CNR di

• VINCENZO BONIFACI (Unità di personale interno)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• Mathematical programming (Rivista)