Lower bounds to the graph partitioning problem through generalized linear programming and network flows

DOI10.1051/ro/1987210403491zbMath0657.90095OpenAlexW2468889070MaRDI QIDQ3807012

No author found.

Publication date: 1987

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/104928

zbMATH Keywords

exact solutionbranch-and-boundgraph partitioningsharp boundspolynomial solvabilitycontinuous relaxationmax-flowcolumn generation subproblemlarge-scale set partitioninglarge-scale Boolean linear programmingquadratic pseudo- Boolean minimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, Cluster analysis and mathematical programming, Image space approach to penalty methods, Improved Lagrangean decomposition: An application to the generalized assignment problem, Topological graph clustering with thin position