A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
DOI10.1137/21M1419775zbMath1500.90044OpenAlexW4293211860WikidataQ114074030 ScholiaQ114074030MaRDI QIDQ5867624
Mykyta Makovenko, Miltiades P. Pardalos, Sergiy I. Butenko
Publication date: 14 September 2022
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/21m1419775
maximum clique problemMotzkin-Straus formulationcontinuous approaches to discrete optimizationstandard polynomial programming
Programming involving graphs or networks (90C35) Graph polynomials (05C31) Nonconvex programming, global optimization (90C26) Polynomial optimization (90C23)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications
- A generalization of the Motzkin-Straus theorem to hypergraphs
- Bounds on the number of complete subgraphs
- On standard quadratic optimization problems
- Clique polynomials and independent set polynomials of graphs
- Evolution towards the maximum clique
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- NP-hardness of deciding convexity of quartic polynomials and related problems
- Continuous cubic formulations for cluster detection problems in networks
- On standard quadratic programs with exact and inexact doubly nonnegative relaxations
- A new trust region technique for the maximum weight clique problem
- Global Optimization with Polynomials and the Problem of Moments
- Approximation of the Stability Number of a Graph via Copositive Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
- On the Maximum Weight Clique Problem
- A global optimization approach for solving the maximum clique problem
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Continuous Characterizations of the Maximum Clique Problem
- Proofs from THE BOOK
- Solving Quadratic Programming by Cutting Planes
- A new branch-and-bound algorithm for standard quadratic programming problems
- Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization
- Reducibility among Combinatorial Problems
- Fast Cluster Detection in Networks by First Order Optimization
- A General Regularized Continuous Formulation for the Maximum Clique Problem
- Why Is Maximum Clique Often Easy in Practice?
- Maxima for Graphs and a New Proof of a Theorem of Turán
- On cliques in graphs
- On copositive programming and standard quadratic optimization problems
This page was built for publication: A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
