Adjacency of the best and second best valued solutions in combinatorial optimization problems
type: Item
instance of: scholarly article
title: Adjacency of the best and second best valued solutions in combinatorial optimization problems
zbMATH Open document ID: 0805.90090
DOI: 10.1016/0166-218X(93)90128-B
author: Tomomi Matsui
author: Akihisa Tamura
author: Yoshiko T. Ikebe
published in: Discrete Applied Mathematics
publication date: 1995-01-31T00:00:00Z
review text: Let \(P\) be a polytope. Given a weight vector \(w\) the \(K\)-best extreme point-problem is to find \(K\) different extreme points \(x_ 1,\dots,x_ k\) of \(P\) such that \(w(x_ 1)\leq\cdots\leq w(x_{k-1})\leq w(x_ k)\) and \(w(x_ k)\leq w(x)\) for all extreme points \(x\neq x_ 1,\dots,x_ k\). A \(K\)-best valued extreme point is an extreme point \(x_ k\) of \(P\) for which there exist extreme points \(x_ 1,\dots,x_{k-1}\) satisfying \(w(x_ 1)<\cdots< w(x_{k-1})< w(x_ k)\) and \(w(x_ k)< w(x)\) for all extreme points \(x\) with \(w(x)\neq w(x_ 1),\dots,w(x_ k)\). A polytope \(P\) is said to satisfy the strong adjacency property if for any weight vector \(w\) every best valued extreme point is adjacent to some second best valued extreme point of \(P\). It is shown that polytopes satisfying the following property \((P_ 1)\) share the strong adjacency property: \((P_ 1)\): for each ordered pair \((x,y)\) of extreme points of \(P\) which are not adjacent there exist other extreme points \(x^ 1,\dots, x^ n\) and positive integers \(\lambda_ 1,\dots,\lambda_ n\) such that \(y- x= \lambda_ 1(x^ 1- x)+\cdots+ \lambda_ n(x^ n- x)\). Combinatorial polytopes (with examples such as perfect matching, binary \(b\)-matching, set partitioning-polytopes or base-polytopes of matroids) are shown to share \((P_ 1)\) and thus the strong adjacency property. Finally, monotone 0-1 polytopes such as matching, stable set or set packing polytopes are also shown to share the strong adjacency property.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 52B05
zbMATH DE Number: 501156
zbMATH Keywords: combinatorial polytopes
zbMATH Keywords: polytope
zbMATH Keywords: \(K\)-best valued extreme point
zbMATH Keywords: strong adjacency property
zbMATH Keywords: perfect matching
zbMATH Keywords: set partitioning-polytopes
zbMATH Keywords: set packing polytopes
reviewed by: Reinhardt Euler
MaRDI profile type: Publication
cites work: Algorithms for finding k-best perfect matchings
cites work: Q3858023
cites work: Algorithms for finding a \(K\)th best valued assignment
cites work: Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
cites work: Hamiltonicity and combinatorial polyhedra
cites work: Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
description: scientific article; zbMATH DE number 501156