A Convex Quadratic Characterization of the Lovász Theta Number

DOI10.1137/S0895480104429181zbMath1089.05048MaRDI QIDQ5470766

Carlos J. Luz, Alexander Schrijver

Publication date: 1 June 2006

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480104429181

zbMATH Keywords

quadratic programming; combinatorial optimization; graph theory; maximum stable set

Mathematics Subject Classification ID

90C20: Quadratic programming

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

Related Items

Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming, A survey on graphs with convex quadratic stability number, New results for recognizing convex-QP adverse graphs, A proximal bundle method for nonsmooth nonconvex functions with inexact information, A characterization of the weighted Lovász number based on convex quadratic programming, Improving an upper bound on the size of \(k\)-regular induced subgraphs, An axiomatic duality framework for the theta body and related convex corners, Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number, A heuristic for the stability number of a graph based on convex quadratic programming and tabu search, Cliques with maximum/minimum edge neighborhood and neighborhood density, Tightening a copositive relaxation for standard quadratic optimization problems, Extended and discretized formulations for the maximum clique problem, A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming, Maximum cut-clique problem: ILS heuristics and a data analysis application, Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms