On the (near) optimality of extended formulations for multi-way cut in social networks

DOI10.1007/S11081-021-09648-6MaRDI QIDQ2129209zbMATH OpenOpenAlexFDO

Authors Chaithanya Bandi, Sunil Chopra, Sangho Shim

Publication date 22 April 2022

Published in Optimization and Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11081-021-09648-6

zbMATH Keywords

integer programmingmultiway cut problemEF2hub-spoke network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Integer programming (90C10)

Recommendations

• Analysis of LP relaxations for multiway and multicut problems
• Extended formulations for the \(A\)-cut problem
• Algorithm Theory - SWAT 2004
• Multiway cuts in node weighted graphs
• On the multiway cut polyhedron

Cites work

• scientific article; zbMATH DE number 5485510 (Why is no real title available?)
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• scientific article; zbMATH DE number 1342124 (Why is no real title available?)
• A Theory of Fairness, Competition, and Cooperation
• A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
• An improved approximation algorithm of MULTIWAY CUT.
• Analysis of LP relaxations for multiway and multicut problems
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Euclidean Hub-and-Spoke Networks
• Extended formulations for the \(A\)-cut problem
• Finding k Cuts within Twice the Optimal
• Multi-Terminal Network Flows
• Multiway cut, pairwise realizable distributions, and descending thresholds
• On the multiway cut polyhedron
• Planar orientations with low out-degree and compaction of adjacency matrices
• Simplex partitioning via exponential clocks and the multiway cut problem
• The Complexity of Multiterminal Cuts

Cited in

(1)

• Modeling and optimization: theory and applications (MOPTA) 2019 -- selected works

This page was built for publication: On the (near) optimality of extended formulations for multi-way cut in social networks

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