ADJACENCY OF THE BEST AND 2ND BEST VALUED SOLUTIONS IN COMBINATORIAL OPTIMIZATION PROBLEMS

Authors
IKEBE Y MATSUI T TAMURA A
Citation
Y. Ikebe et al., ADJACENCY OF THE BEST AND 2ND BEST VALUED SOLUTIONS IN COMBINATORIAL OPTIMIZATION PROBLEMS, Discrete applied mathematics, 47(3), 1993, pp. 227-232
Citations number
6
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
47
Issue
3
Year of publication
1993
Pages
227 - 232
Database
ISI
Abstract
We say that a polytope satisfies the strong adjacency property if ever y best valued extreme point of the polytope is adjacent to some second best valued extreme point for any weight vector. Perfect matching pol ytopes satisfy this property. In this paper, we give sufficient condit ions for a polytope to satisfy the strong adjacency property. From thi s, binary b-matching polytopes, set partitioning polytopes, set packin g polytopes, etc. satisfy the strong adjacency property.