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 (19)

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 ⋮ On convergence of the generalized Lanczos trust-region method for trust-region subproblems ⋮ 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

This page was built for publication: Graph Partitioning and Continuous Quadratic Programming