On LP-based approximation for copositive formulation of stable set problem

DOI10.14495/JSIAML.7.69MaRDI QIDQ3121395zbMATH OpenOpenAlexFDO

Authors Katsuya Tono

Publication date 18 March 2019

Published in JSIAM Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.14495/jsiaml.7.69

zbMATH Keywords

copositive programmingheuristicslinear programmingMotzkin-Straus theoremstable set problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation of the stability number of a graph via copositive programming
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• scientific article; zbMATH DE number 1594513
• On the accuracy of uniform polyhedral approximations of the copositive cone
• Copositive programming motivated bounds on the stability and the chromatic numbers

Cites work

• Approximation of the stability number of a graph via copositive programming
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On the Shannon capacity of a graph
• Reducibility among combinatorial problems
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Some NP-complete problems in quadratic and nonlinear programming

Cited in

(3)

• Approximation of the stability number of a graph via copositive programming
• Persistency of linear programming relaxations for the stable set problem
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming

This page was built for publication: On LP-based approximation for copositive formulation of stable set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3121395)