Analysis of Lagrangian Lower Bounds for a Graph Partitioning Problem

DOI10.1287/OPRE.47.5.785MaRDI QIDQ4950824zbMATH OpenOpenAlexFDO

Authors Jay B. Ghosh, Gajendra Kumar Adil

Publication date 27 April 2000

Published in Operations Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11693/25215

zbMATH Keywords

graph partitioning problemsLagrangian relaxationmixed integer programming

Mathematics Subject Classification ID

Applications of graph theory (05C90) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 4029297
• Lower bounds to the graph partitioning problem through generalized linear programming and network flows
• Problème de la bipartition minimale d'un graphe
• On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions
• On the solution of a graph partitioning problem under capacity constraints

Cited in

(2)

• Lagrangian relaxation and pegging test for the clique partitioning problem
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems

This page was built for publication: Analysis of Lagrangian Lower Bounds for a Graph Partitioning Problem

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