Adjacency of the best and second best valued solutions in combinatorial optimization problems

Adjacency of the best and second best valued solutions in combinatorial optimization problems

0.00 Avg rating0 Votes
Article ID: iaor1995310
Country: Netherlands
Volume: 47
Issue: 3
Start Page Number: 227
End Page Number: 232
Publication Date: Dec 1993
Journal: Discrete Applied Mathematics
Authors: , ,
Keywords: combinatorial analysis
Abstract:

The authors say that a polytope satisfies the strong adjacency property if every best valued extreme point of the polytope is adjacent to some second best valued extreme point for any weight vector. Perfect matching polytopes satisfy this property. In this paper, the authors give sufficient conditions for a polytope to satisfy the strong adjacency property. From this, binary b-matching polytopes, set partitioning polytopes, set packing polytopes, etc. satisfy the strong adjacency property.

Reviews

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