Analysis of LP relaxations for multiway and multicut problems

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1097-0037(199909)34:2<102::AID-NET3>3.0.CO;2-X" /><102::AID-NET3>3.0.CO;2-X 10.1002/(SICI)1097-0037(199909)34:2<102::AID-NET3>3.0.CO;2-XzbMath0959.90061OpenAlexW1971654255MaRDI QIDQ4267390

Chung-Piaw Teo, Dimitris J. Bertsimas, Rakesh V. Vohra

Publication date: 4 October 1999

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199909)34:2<102::aid-net3>3.0.co;2-x

zbMATH Keywords

randomized roundingLP relaxationmulticut problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

On the (near) optimality of extended formulations for multi-way cut in social networks ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Multiway cut and integer flow problems in trees

Cites Work

• Topics on perfect graphs
• Geometric algorithms and combinatorial optimization

This page was built for publication: Analysis of LP relaxations for multiway and multicut problems