Ideal polytopes and face structures of some combinatorial optimization problems

Ideal polytopes and face structures of some combinatorial optimization problems

0.00 Avg rating0 Votes
Article ID: iaor19971077
Country: Netherlands
Volume: 71
Issue: 1
Start Page Number: 1
End Page Number: 15
Publication Date: Nov 1995
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: combinatorial optimization
Abstract:

Given a finite set X and a family of ‘feasible’ subsets ℱ of X, the 0-1 polytope P(ℱ) is defined as the convex hull of all the characteristic vectors of members of ℱ. The authors show that under a certain assumption a special type of face of P(ℱ) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, the authors propose a new heuristic for such problems and give results of the present preliminary computational experiments for the maximum stable set problem.

Reviews

Required fields are marked *. Your email address will not be published.