Multiway cut, pairwise realizable distributions, and descending thresholds

DOI10.1145/2591796.2591866zbMath1315.68288arXiv1309.2729OpenAlexW2060121592MaRDI QIDQ5259608

Ankit Sharma, Jan Vondrák

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.2729

zbMATH Keywords

approximation algorithmmultiway cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (21)

Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts ⋮ On the (near) optimality of extended formulations for multi-way cut in social networks ⋮ Experimental evaluation of a local search approximation algorithm for the multiway cut problem ⋮ Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems ⋮ \(\ell_p\)-norm multiway cut ⋮ Global and fixed-terminal cuts in digraphs ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Vertex downgrading to minimize connectivity ⋮ A local search approximation algorithm for the multiway cut problem ⋮ Geometric multicut: shortest fences for separating groups of objects in the plane ⋮ Approximation Algorithms for CSPs ⋮ Approximating Requirement Cut via a Configuration LP ⋮ Improved approximation algorithms for the maximum happy vertices and edges problems ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ A simple algorithm for the multiway cut problem ⋮ Improving the integrality gap for multiway cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Beating the 2-approximation factor for global bicut ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Approximation algorithms for vertex happiness ⋮ Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Multiway cut, pairwise realizable distributions, and descending thresholds