Analysis of LP relaxations for multiway and multicut problems

DOI10.1002/(SICI)1097-0037(199909)34:2%3C102::AID-NET3%3E3.0.CO;2-XMaRDI QIDQ4267390zbMATH OpenOpenAlexFDO

Authors Chung-Piaw Teo, Dimitris 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%3C102::aid-net3%3E3.0.co;2-x

zbMATH Keywords

LP relaxationmulticut problemsrandomized rounding

Mathematics Subject Classification ID

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

Recommendations

• Nonlinear formulations and improved randomized approximation algorithms for multicut problems
• scientific article; zbMATH DE number 1775387
• Multiway cuts in node weighted graphs

Cites work

• Geometric algorithms and combinatorial optimization
• Topics on perfect graphs

Cited in

(5)

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

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

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