Graph Partitioning and Continuous Quadratic Programming

DOI10.1137/S0895480199335829zbMath0972.90086OpenAlexW2086079401MaRDI QIDQ4699174

Yaroslav Krylyuk, William W. Hager

Publication date: 23 November 1999

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480199335829

zbMATH Keywords

quadratic programmingoptimality conditionsgraph partitioningFiedler vectormax-cutgraph Laplacianmin-cutedge separators

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

Continuous quadratic programming formulations of optimization problems on graphs, A Nested Lanczos Method for the Trust-Region Subproblem, Systematic and deterministic graph minor embedding for Cartesian products of graphs, An exact algorithm for graph partitioning, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, On the Generalized Lanczos Trust-Region Method, Linear and quadratic programming approaches for the general graph partitioning problem, Constructing test functions for global optimization using continuous formulations of graph problems, Optimality conditions for maximizing a function over a polyhedron, A practical method for solving large-scale TRS, Global convergence of SSM for minimizing a quadratic over a sphere, Error bounds of Lanczos approach for trust-region subproblem, Two new integer linear programming formulations for the vertex bisection problem, Discrete Optimization with Decision Diagrams, Advanced Coarsening Schemes for Graph Partitioning, Variable fixing method by weighted average for the continuous quadratic knapsack problem, The Convergence of the Generalized Lanczos Trust-Region Method for the Trust-Region Subproblem, An Efficient Hybrid Algorithm for the Separable Convex Quadratic Knapsack Problem

Uses Software

• MESHPART
• NAPACK