A multilevel bilinear programming algorithm for the vertex separator problem
From MaRDI portal
Publication:683341
DOI10.1007/S10589-017-9945-2zbMATH Open1394.90546arXiv1410.4885OpenAlexW2963883456MaRDI QIDQ683341FDOQ683341
Authors: William Hager, James T. Hungerford, Ilya Safro 
Publication date: 6 February 2018
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Abstract: The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. In the paper 10.1016/j.ejor.2014.05.042, the Vertex Separator Problem was formulated as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. A Mountain Climbing Algorithm is used to find a stationary point of the continuous bilinear quadratic program, while second-order optimality conditions and perturbation techniques are used to escape from either a stationary point or a local maximizer. The algorithms for solving the continuous bilinear program are employed during the solution and refinement phases in a multilevel scheme. Computational results and comparisons demonstrate the advantage of the proposed algorithm.
Full work available at URL: https://arxiv.org/abs/1410.4885
Recommendations
- The vertex separator problem: a polyhedral investigation
- Continuous quadratic programming formulations of optimization problems on graphs
- An exact algorithm for solving the vertex separator problem
- The vertex separator problem: algorithms and computations
- Exact algorithms for the vertex separator problem in graphs
multilevelgraph partitioningvertex separatormultilevel algorithmcontinuous formulationweighted edge contractions
Quadratic programming (90C20) Large-scale problems in mathematical programming (90C06) Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)
Cites Work
- The University of Florida sparse matrix collection
- Direct Methods for Sparse Linear Systems
- An efficient hybrid algorithm for the separable convex quadratic knapsack problem
- Title not available (Why is that?)
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Title not available (Why is that?)
- An Efficient Heuristic Procedure for Partitioning Graphs
- Finding good approximate vertex and edge partitions is NP-hard
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- Breakout local search for the quadratic assignment problem
- Advanced coarsening schemes for graph partitioning
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- A cutting plane algorithm for solving bilinear programs
- Linear programming. Foundations and extensions
- A parallel graph partitioning algorithm for a message-passing multiprocessor
- Graph minimum linear arrangement by multilevel weighted edge contractions
- Title not available (Why is that?)
- Relaxation-based coarsening and multiscale graph organization
- Algebraic distance on graphs
- NP-completeness of the Planar Separator Problems
- Geometric Separators for Finite-Element Meshes
- Optimality conditions for maximizing a function over a polyhedron
- Continuous quadratic programming formulations of optimization problems on graphs
- Partitioning hypergraphs in scientific computing applications through vertex separators on graphs
- Title not available (Why is that?)
- A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap
- The MIN-cut and vertex separator problem
Cited In (12)
- The MIN-cut and vertex separator problem
- The multi-terminal vertex separator problem: branch-and-cut-and-price
- Relaxation-based coarsening for multilevel hypergraph partitioning
- A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
- Continuous quadratic programming formulations of optimization problems on graphs
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- Two new integer linear programming formulations for the vertex bisection problem
- Multilevel graph partitioning for three-dimensional discrete fracture network flow simulations
- A note on the SDP relaxation of the minimum cut problem
- The vertex separator problem: algorithms and computations
- An efficient hybrid algorithm for the separable convex quadratic knapsack problem
Uses Software
This page was built for publication: A multilevel bilinear programming algorithm for the vertex separator problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683341)
