Nonlinear formulations and improved randomized approximation algorithms for multicut problems

DOI10.1007/3-540-59408-6_39zbMath1498.90136OpenAlexW1759795344MaRDI QIDQ5101403

Chung-Piaw Teo, Dimitris J. 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

perfect graphrounding heuristicmaximum weighted independent set problem

Mathematics Subject Classification ID

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

Related Items (6)

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

Cites Work

• Unnamed Item
• Topics on perfect graphs
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Geometric algorithms and combinatorial optimization
• On weighted multiway cuts in trees
• Extended formulations for the \(A\)-cut problem
• On the multiway cut polyhedron
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Facial Structure of the Set of Correlation Matrices
• Approximate max-flow min-(multi)cut theorems and their applications

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