Constant factor approximation for balanced cut in the PIE model

DOI10.1145/2591796.2591841MaRDI QIDQ5259537zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

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/1406.5665

zbMATH Keywords

approximation algorithmaverage-case analysisbalanced cutrandom planted modelsemi-random model

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than planted models considered previously. Consider a set of vertices V partitioned into two clusters $L$ and $R$ of equal size. Let $G$ be an arbitrary graph on $V$ with no edges between $L$ and $R$. Let $E_{random}$ be a set of edges sampled from an arbitrary permutation-invariant distribution (a distribution that is invariant under permutation of vertices in $L$ and in $R$). Then we say that $G+E_{random}$ is a graph with permutation-invariant random edges. We present an approximation algorithm for the Balanced Cut problem that finds a balanced cut of cost $O(|E_{random}|)+nextpolylog(n)$ in this model. In the regime when $|E_{random}|=Omega(nextpolylog(n))$, this is a constant factor approximation with respect to the cost of the planted cut.

Recommendations

• Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem
• Constant ratio fixed-parameter approximation of the edge multicut problem
• Proportional pie-cutting
• Balanced cut approximation in random geometric graphs
• Balanced Cut Approximation in Random Geometric Graphs
• Approximating Maximum Cut with Limited Unbalance
• Cake cutting algorithms for piecewise constant and piecewise uniform valuations
• An approximate distribution for the normalized cut
• Approximation by piecewise constants on convex partitions
• scientific article; zbMATH DE number 1947449

Cites work

• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(12)

• Detecting communities is hard (and counting them is even harder)
• A geometric protocol for cryptography with cards
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Low rank approximation in the presence of outliers
• Stability and recovery for independence systems
• Approximation algorithms for semi-random partitioning problems
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• A distributed computing perspective of unconditionally secure information transmission in Russian cards problems
• Planted models for the densest k-subgraph problem
• Average-case and smoothed analysis of graph isomorphism
• Exact recovery of planted cliques in semi-random graphs
• Independent sets in semi-random hypergraphs

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Constant factor approximation for balanced cut in the PIE model

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