Antiweb-wheel inequalities and their separation problems over the stable set polytopes
type: Item
instance of: scholarly article
title: Antiweb-wheel inequalities and their separation problems over the stable set polytopes
zbMATH Open document ID: 1154.90604
author: Eddie Cheng
author: Sven De Vries
published in: Mathematical Programming. Series A. Series B
publication date: 2002-06-12T00:00:00Z
review text: The problem of finding a maximum weight stable set problem of a graph \(G\) can be formulated as the problem of optimizing a linear function over the convex hull \(\text{STAB}(G)\) of incidence vectors of stable sets. It is impossible (unless \(\mathcal {NP}=co\;\mathcal {NP}\)) to obtain a ``concise'' characterization of \(\text{STAB}(G)\) as the solution set of a system of linear inequalities, and one of the approaches is to find large classes of valid inequalities with the property that the corresponding separation problem (given a point \(x^*\), find, if possible, an inequality in the class that \(x^*\) violates) is efficiently solvable. The authors give a polynomial time separation algorithm for the \((t)\)-antiweb inequalities of \textit{L. E. Trotter jun.} [Discrete Math. 12, 373--388 (1975; Zbl 0314.05111)] and for some larger classes of valid inequalities.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1754745
zbMATH Keywords: maximum weight stable set
zbMATH Keywords: antiweb-wheel inequalities.
reviewed by: Fedor V. Fomin
MaRDI profile type: Publication
full work available at URL: s101070100267
OpenAlex ID: W2090665905
DOI: 10.1007/S101070100267
description: scientific article; zbMATH DE number 1754745