Affordable Access

Publisher Website

Edmonds polytopes and a hierarchy of combinatorial problems

Discrete Mathematics
Publication Date
DOI: 10.1016/0012-365x(73)90167-2
  • Computer Science


Abstract Let S be a set of linear inequalities that determine a bounded polyhedron P. The closure of S is the smallest set of inequalities that contain S and is closed under two operations: (i) taking linear combinations of inequalities, (ii) replacing an inequality Σ a j x j ≤ a 0, where a 1, a 2,…, a n are integers, by the inequality Σa j x j ≤ a with a ≥ [ a 0]. Obviously, if integers x 1, x 2,…, x n satisfy all the inequalities in S, then they satisfy also all inequalities in the closure of S. Conversely, let Σc j x j ≤ c 0 hold for all choices of integers x 1, x 2,…, x n that satisfy all the inequalities in S. Then we prove that Σc j x j ≤ c 0 belongs to the closure of S. To each integer linear programming problem, we assign a nonnegative integer, called its rank. (The rank is the minimum number of iterations of the operation (ii) that are required in order to eliminate the integrality constraint.) We prove that there is no upper bound on the rank of problems arising from the search for largest independent sets in graphs.

There are no comments yet on this publication. Be the first to share your thoughts.