×

Near-perfect graphs with polyhedral \(N_+(G)\). (English) Zbl 1268.90031

Bonomo, Flavia (ed.) et al., LAGOS’11 – VI Latin-American algorithms, graphs, and optimization symposium. Extended abstracts from the symposium, Bariloche, Argentina, March 28–April 1, 2011. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 37, 393-398 (2011).
Summary: One of the beautiful results due to Grötschel, Lovász and Schrijver is the fact that the theta body of a graph \(G\) is polyhedral if and only if \(G\) is perfect. Related to the theta body of \(G\) is a foundational construction of an operator on polytopes, called \(N_{+}(\cdot)\), by Lovász and Schrijver. Here, we initiate the pursuit of a characterization theorem analogous to the one above by Grötschel, Lovász and Schrijver, replacing the theta body of \(G\) by \(N_{+}(G)\) and searching for the combinatorial counterpart to replace the class of perfect graphs.
For the entire collection see [Zbl 1239.05004].

MSC:

90C10 Integer programming
05C85 Graph algorithms (graph-theoretic aspects)
90C22 Semidefinite programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Bianchi, M. Escalante, G. Nasini, L.Tunçel, Some advances on Lovász-Schrijver \(N_+(\cdot)\); S. Bianchi, M. Escalante, G. Nasini, L.Tunçel, Some advances on Lovász-Schrijver \(N_+(\cdot)\) · Zbl 1268.90130
[2] Escalante, M.; Montelar, M. S.; Nasini, G., Minimal \(N_+\)-rank graphs: Progress on Lipták and Tunçelʼs conjecture, Operations Research Letters, 34, 6, 639-646 (2006) · Zbl 1109.05098
[3] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056
[4] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial, Optimization (1988), Springer: Springer New York · Zbl 0634.05001
[5] Lipták, L.; Tunçel, L., Stable set problem and the lift-and-project ranks of graphs, Math. Program., 98, 319-353 (2003) · Zbl 1160.90584
[6] Lovász, L., On the Shannon capacity of a graph, IEEE Transactions, 25, 1-7 (1979) · Zbl 0395.94021
[7] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190 (1991) · Zbl 0754.90039
[8] Shepherd, F. B., Near-Perfect matrices, Math. Programming, 1-3, 64, 295-323 (1994) · Zbl 0804.05036
[9] Shepherd, F. B., Applying Lehmanʼs theorems to packing problems, Math. Programming, 71, 353-367 (1995) · Zbl 0863.05052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.