On Linear Characterizations of Combinatorial Optimization Problems I: A Small Facial Description in NP Puts the Decision Problem in co-NPResearch Paper
Polyhedral combinatorics attacks a combinatorial optimization problem by replacing its finite set of feasible solutions with the convex hull of that set and describing the hull by linear inequalities. Once such a description is known, the problem becomes a linear program, and linear programming duality supplies optimality certificates. For matchings,…