TY - JOUR
T1 - Adjacency of the best and second best valued solutions in combinatorial optimization problems
AU - Ikebe, Yoshiko
AU - Matsui, Tomomi
AU - Tamura, Akihisa
PY - 1993/12/21
Y1 - 1993/12/21
N2 - We 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, we 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.
AB - We 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, we 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.
UR - http://www.scopus.com/inward/record.url?scp=43949162474&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=43949162474&partnerID=8YFLogxK
U2 - 10.1016/0166-218X(93)90128-B
DO - 10.1016/0166-218X(93)90128-B
M3 - Article
AN - SCOPUS:43949162474
SN - 0166-218X
VL - 47
SP - 227
EP - 232
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 3
ER -