A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

DOI10.1016/j.orl.2020.10.009OpenAlexW3097322038MaRDI QIDQ2661585

Yanyan Li

Publication date: 7 April 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11820/55008dee-fead-402c-8d2e-c2bdd5c7efd0

zbMATH Keywords

maximum independent setpolynomial optimizationLasserre hierarchydual bounds

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (1)

Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems

Cites Work

• Unnamed Item
• Semidefinite programming for discrete optimization and matrix completion problems
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• Integer Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

This page was built for publication: A note on the Lasserre hierarchy for different formulations of the maximum independent set problem