On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions

DOI10.1007/BF02032129zbMath0836.90143OpenAlexW2038724917MaRDI QIDQ1904713

Michel Minoux

Publication date: 7 January 1996

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02032129

zbMATH Keywords

graph partitioning problemlarge-scale linear programming relaxationsmaximum cost ratio subset

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Large-scale problems in mathematical programming (90C06) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• A simple version of Karzanov's blocking flow algorithm
• The ellipsoid method and its consequences in combinatorial optimization
• A fast algorithm for the generalized parametric minimum cut problem and applications
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• On the supermodular knapsack problem
• A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
• Lower bounds to the graph partitioning problem through generalized linear programming and network flows
• A new approach to the maximum-flow problem
• Combinatorial Optimization with Rational Objective Functions
• A Fast Parametric Maximum Flow Algorithm and Applications

This page was built for publication: On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions