Improved linearized models for graph partitioning problem under capacity constraints

DOI10.1080/10556788.2016.1230209MaRDI QIDQ4594838zbMATH OpenOpenAlexFDO

Authors Viet Hung Nguyen, Michel Minoux

Publication date 24 November 2017

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://hal.sorbonne-universite.fr/hal-01369135/file/Nguyen_2017_Improved_linearized.pdf

zbMATH Keywords

\(0/1\) quadratically constrained programmingbranch-and-boundcapacity constraintgraph partitioninglinearization techniques

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• On the solution of a graph partitioning problem under capacity constraints
• Improved approximation algorithms for maximum graph partitioning problems
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Graph partitioning using linear and semidefinite programming
• Linear and quadratic programming approaches for the general graph partitioning problem
• Approximation algorithms for maximization problems arising in graph partitioning
• Lower bounds to the graph partitioning problem through generalized linear programming and network flows
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
• The node capacitated graph partitioning problem: A computational study
• A linear time algorithm for graph partition problems

Cited in

(3)

• An approximation algorithm for graph partitioning via deterministic annealing neural network
• On the solution of a graph partitioning problem under capacity constraints
• Stochastic graph partitioning: quadratic versus SOCP formulations

This page was built for publication: Improved linearized models for graph partitioning problem under capacity constraints

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