A compact linear program for testing optimality of perfect matching (Articolo in rivista)

Type
Label
  • A compact linear program for testing optimality of perfect matching (Articolo in rivista) (literal)
Anno
  • 2003-01-01T00:00:00+01:00 (literal)
Alternative label
  • Ventura, P.; Eisenbrand, F. (2003)
    A compact linear program for testing optimality of perfect matching
    in Operations research letters
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Ventura, P.; Eisenbrand, F. (literal)
Pagina inizio
  • 429 (literal)
Pagina fine
  • 434 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 31 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • Ventura, P.: Istituto di Analisi dei Sistemi ed Informatica \"A. Ruberti\" - CNR -- Eisenbrand, F.: Max Plank Institut fuer Informatik, Saarbrucken, Germany (literal)
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • A compact linear program for testing optimality of perfect matching (literal)
Abstract
  • It is a longstanding open problem whether there exists a polynomial size description of the perfect matching polytope. We give a partial answer to this question by proving the following result. The polyhedron defined by the constraints of the perfect matching polytope which are active at a given perfect matching can be obtained as the projection of a compact polyhedron. Thus there exists a compact linear program which is unbounded if and only if the perfect matching is not optimal with respect to a given edge weight. This result provides a simple reduction of the maximum weight perfect matching problem to compact linear programming. (literal)
Prodotto di
Autore CNR

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it