Graph Partitioning and Continuous Quadratic Programming

DOI10.1137/S0895480199335829zbMATH Open0972.90086OpenAlexW2086079401MaRDI QIDQ4699174FDOQ4699174

Authors: William Hager, Yaroslav Krylyuk 

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

Recommendations

• Linear and quadratic programming approaches for the general graph partitioning problem
• Graph partitioning using linear and semidefinite programming
• scientific article; zbMATH DE number 995811
• scientific article; zbMATH DE number 5761786
• Stochastic graph partitioning: quadratic versus SOCP formulations
• A Copositive Programming Approach to Graph Partitioning
• Semidefinite programming relaxations for the graph partitioning problem
• scientific article; zbMATH DE number 736319
• scientific article; zbMATH DE number 1182569
• Continuous quadratic programming formulations of optimization problems on graphs

zbMATH Keywords

quadratic programminggraph partitioningoptimality conditionsmax-cutgraph LaplacianFiedler vectormin-cutedge separators

Mathematics Subject Classification ID

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

Cited In (26)

• Variable fixing method by weighted average for the continuous quadratic knapsack problem
• A practical method for solving large-scale TRS
• Constrained graph partitioning via matrix differential equations
• Constructing test functions for global optimization using continuous formulations of graph problems
• Continuous graph partitioning for camera network surveillance
• Optimal allocation problem with quadratic utility functions and its relationship with graph cut problem
• Error bounds of Lanczos approach for trust-region subproblem
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
• Multiset graph partitioning
• Optimality conditions for maximizing a function over a polyhedron
• Lovász extension and graph cut
• Continuous quadratic programming formulations of optimization problems on graphs
• On the generalized Lanczos trust-region method
• The convergence of the generalized Lanczos trust-region method for the trust-region subproblem
• Graph separation techniques for quadratic zero-one programming
• Systematic and deterministic graph minor embedding for Cartesian products of graphs
• Discrete optimization with decision diagrams
• Two new integer linear programming formulations for the vertex bisection problem
• Title not available (Why is that?)
• Global convergence of SSM for minimizing a quadratic over a sphere
• On convergence of the generalized Lanczos trust-region method for trust-region subproblems
• A Nested Lanczos Method for the Trust-Region Subproblem
• An exact algorithm for graph partitioning
• Linear and quadratic programming approaches for the general graph partitioning problem
• Advanced coarsening schemes for graph partitioning
• 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

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