A new trust region technique for the maximum weight clique problem

DOI10.1016/J.DAM.2005.04.010MaRDI QIDQ2433799zbMATH OpenOpenAlexFDO

Authors Stanislav Busygin

Publication date 30 October 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.04.010

zbMATH Keywords

quadratic programmingheuristictrust regionmaximum weight cliqueMotzkin-Straus theorem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Traffic problems in operations research (90B20)

Recommendations

• A new branch-and-bound algorithm for the maximum weighted clique problem
• A new algorithm for the maximum-weight clique problem
• scientific article; zbMATH DE number 1786225
• A new upper bound for the maximum weight clique problem
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• Clustered maximum weight clique problem: algorithms and empirical analysis
• On a continuous approach for the maximum weighted clique problem
• A New Approach for Solving the Maximum Clique Problem
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• A complementary pivoting approach to the maximum weight clique problem

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3388498 (Why is no real title available?)
• scientific article; zbMATH DE number 956843 (Why is no real title available?)
• A complementary pivoting approach to the maximum weight clique problem
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• An augmentation algorithm for the maximum weighted stable set problem
• Computing a Trust Region Step
• Continuous Characterizations of the Maximum Clique Problem
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• Local minima of the trust region problem
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Maximum stable set formulations and heuristics based on continuous optimization
• Minimizing a quadratic over a sphere
• On the Stationary Values of a Second-Degree Polynomial on the Unit Sphere
• The complexity of the matrix eigenproblem

Cited in

(41)

• Continuous cubic formulations for cluster detection problems in networks
• Phased local search for the maximum clique problem
• On a continuous approach for the maximum weighted clique problem
• SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
• Exact solution of graph coloring problems via constraint programming and column generation
• Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs
• Some Motzkin-Straus type results for non-uniform hypergraphs
• Subgraph extraction and metaheuristics for the maximum clique problem
• On graph-Lagrangians of hypergraphs containing dense subgraphs
• On Lagrangians of \(r\)-uniform hypergraphs
• Maximum cliques of hypergraphs and polynomial optimization
• A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
• A generalization of the Motzkin-Straus theorem to hypergraphs
• An exact bit-parallel algorithm for the maximum clique problem
• A tutorial on branch and cut algorithms for the maximum stable set problem
• A linear-time algorithm for trust region problems
• Solving the maximum vertex weight clique problem via binary quadratic programming
• A Max-SAT Inference-Based Pre-processing for Max-Clique
• An adaptive multistart tabu search approach to solve the maximum clique problem
• A simple simulated annealing algorithm for the maximum clique problem
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• PUSH: A generalized operator for the maximum vertex weight clique problem
• On the largest graph-Lagrangian of 3-graphs with fixed number of edges
• An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• On cliques and Lagrangians of hypergraphs
• A Motzkin-Straus type result for 3-uniform hypergraphs
• A hybrid heuristic for the maximum clique problem
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Multi-neighborhood tabu search for the maximum weight clique problem
• A continuous characterization of the maximum vertex-weighted clique in hypergraphs
• The stable set problem: clique and nodal inequalities revisited
• Permutation codes with specified packing radius
• On Motzkin-Straus type results for non-uniform hypergraphs
• Sublinear-time quadratic minimization via spectral decomposition of matrices
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• A review on algorithms for maximum clique problems
• Approximate dynamic programming based on high dimensional model representation
• On the maxima of Motzkin-Straus programs and cliques of graphs
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• Finding quasi core with simulated stacked neural networks

Describes a project that uses

Uses Software

• BRENT
• GQTPAR
• Max-AO
• QUALEX
• nauty

This page was built for publication: A new trust region technique for the maximum weight clique problem

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