Approximating \(k\)-cuts using network strength as a Lagrangean relaxation

DOI10.1016/j.ejor.2007.01.040zbMath1138.90023OpenAlexW2030460280MaRDI QIDQ2462107

Amitabh Sinha, R. Ravi

Publication date: 23 November 2007

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.01.040

zbMATH Keywords

Lagrangean relaxationgraph theory

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (9)

Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ An exact model for cell formation in group technology ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Unnamed Item ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the \(k\)-cut problem
• Emergence of Scaling in Random Networks
• Optimal attack and reinforcement of a network
• Finding k Cuts within Twice the Optimal
• A new approach to the minimum cut problem

This page was built for publication: Approximating \(k\)-cuts using network strength as a Lagrangean relaxation