Nonlinear formulations and improved randomized approximation algorithms for multicut problems
From MaRDI portal
Publication:5101403
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
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