2 papers
math.OC2024
Application of the Lovász-Schrijver Lift-and-Project Operator to Compact Stable Set Integer Programs
Federico Battista, Fabrizio Rossi, Stefano Smriglio
The Lovász theta function provides a very good upper bound on the stability number of a graph . It can be computed in polynomial time by solving a semidefinite program (S…
math.OC2021
Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems
Federico Battista, Marianna De Santis
Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become imprac…