A general regularized continuous formulation for the maximum clique problem

DOI10.1287/MOOR.2018.0954MaRDI QIDQ5108235zbMATH OpenOpenAlexWikidataFDO

Authors James T. Hungerford, F. Rinaldi

Publication date 30 April 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.02486

zbMATH Keywords

concave minimizationmaximum cliqueMotzkin-Straussparse optimizationsupport

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonlinear programming (90C30) Programming involving graphs or networks (90C35)

Abstract: In this paper, we develop a general regularization-based continuous optimization framework for the maximum clique problem. In particular, we consider a broad class of regularization terms that can be included in the classic Motzkin-Strauss formulation and we develop conditions that guarantee the equivalence between the continuous regularized problem and the original one in both a global and a local sense. We further analyze, from a computational point of view, two different regularizers that satisfy the general conditions.

Recommendations

• scientific article; zbMATH DE number 2102015
• scientific article; zbMATH DE number 1560332
• scientific article; zbMATH DE number 956845
• On a continuous approach for the maximum weighted clique problem
• Continuous Characterizations of the Maximum Clique Problem

Cites work

• A generalization of the Motzkin-Straus theorem to hypergraphs
• A global optimization approach for solving the maximum clique problem
• A review on algorithms for maximum clique problems
• Annealed replication: A new heuristic for the maximum clique problem
• Checking local optimality in constrained quadratic programming is NP- hard
• Continuous Characterizations of the Maximum Clique Problem
• Copositivity for second-order optimality conditions in general smooth optimization problems
• Evolution towards the maximum clique
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• scientific article; zbMATH DE number 956845 (Why is no real title available?)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On solving the maximum clique problem
• Optimality conditions for maximizing a function over a polyhedron
• Parsimonious least norm approximation
• Reducibility among combinatorial problems
• Some NP-complete problems in quadratic and nonlinear programming

Cited in

(13)

• On the maxima of Motzkin-Straus programs and cliques of graphs
• Continuous cubic formulations for cluster detection problems in networks
• Frank-Wolfe and friends: a journey into projection-free first-order optimization methods
• scientific article; zbMATH DE number 2102015 (Why is no real title available?)
• Fast cluster detection in networks by first order optimization
• Finite convergence of sum-of-squares hierarchies for the stability number of a graph
• A Continuous-Based Approach for Partial Clique Enumeration
• scientific article; zbMATH DE number 956845 (Why is no real title available?)
• A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
• Regularized standard polynomial programming formulations for the maximum clique problem
• A square departure from symmetry in matrix cones
• Mixed-integer bilevel optimization with nonconvex quadratic lower-level problems: complexity and a solution method
• On generalized KKT points for the Motzkin-Straus program

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: A general regularized continuous formulation for the maximum clique problem

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