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

DOI10.1007/S11081-021-09648-6zbMATH Open1485.90071OpenAlexW3179000988MaRDI QIDQ2129209FDOQ2129209

Sangho Shim, Chaithanya Bandi, Sunil Chopra

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Planar orientations with low out-degree and compaction of adjacency matrices
• A Theory of Fairness, Competition, and Cooperation
• The Complexity of Multiterminal Cuts
• Simplex partitioning via exponential clocks and the multiway cut problem
• Rounding algorithms for a geometric embedding of minimum 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
• Multi-Terminal Network Flows
• On the multiway cut polyhedron
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Finding k Cuts within Twice the Optimal
• Analysis of LP relaxations for multiway and multicut problems
• An improved approximation algorithm of MULTIWAY CUT.
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Extended formulations for the \(A\)-cut problem
• Euclidean Hub-and-Spoke Networks

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)