Campus Event Calendar
Event Entry
What and Who
A compact linear programming formulation for testing optimality of perfect matchings
Paolo Ventura
MPI SB and IASI ROMA
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 5 April 2002
13:30
30 Minutes
Warning: Date has changed!
46.1 - MPII
024
Saarbrücken
Abstract
We present a compact linear program for the problem of testing whether
a given perfect matching of a graph is of maximal weight with respect
to given edge weights. More precisely, we show that the cone 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
polyhedron which can be described with a polynomial number of
variables and inequalities. This result provides a simple reduction
of the maximum weight perfect matching problem to compact linear
programming.
Contact
Friedrich Eisenbrand
--email hidden
passcode not visible
logged in users only