Reducing Matching to Polynomial Size Linear Programming

摘要: The question of whether the maximum weight matching problem can be reduced to a linear program polynomial size is studied. A partial answer it given; i.e., shown that Chinese postman (and optimum matching) reduces sequence $O( m^2 \log n )$ minimum mean cycle problems. It this last formulated as size. This gives algorithm for based on any method programming. combinatorial finding cycles in undirected graphs also given.