Nonlinear formulations and improved randomized approximation algorithms for multicut problems

DOI10.1007/3-540-59408-6_39MaRDI QIDQ5101403zbMATH OpenOpenAlexFDO

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

Publication date 30 August 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59408-6_39

zbMATH Keywords

maximum weighted independent set problemperfect graphrounding heuristic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Analysis of LP relaxations for multiway and multicut problems
• Algorithm Theory - SWAT 2004
• scientific article; zbMATH DE number 1775387
• The multi-multiway cut problem

Cites work

• Approximate max-flow min-(multi)cut theorems and their applications
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Extended formulations for the \(A\)-cut problem
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• On the Facial Structure of the Set of Correlation Matrices
• On the multiway cut polyhedron
• On weighted multiway cuts in trees
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Topics on perfect graphs

Cited in

(7)

• Minimum multiway cuts in trees
• An improved approximation algorithm of MULTIWAY CUT.
• A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
• Analysis of LP relaxations for multiway and multicut problems
• On dependent randomized rounding algorithms
• Improved randomized approximation algorithms for lot-sizing problems
• Approximation algorithms for feasible cut and multicut problems

This page was built for publication: Nonlinear formulations and improved randomized approximation algorithms for multicut problems

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