Minimizing the union: tight approximations for small set bipartite vertex expansion

DOI10.1137/1.9781611974782.56MaRDI QIDQ4575795zbMATH OpenOpenAlexFDO

Authors Eden Chlamtac, Michael Dinitz, Yury Makarychev

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Hypergraphs (05C65)

Abstract: In the Minimum k-Union problem (MkU) we are given a set system with n sets and are asked to select k sets in order to minimize the size of their union. Despite being a very natural problem, it has received surprisingly little attention: the only known approximation algorithm is an $O(sqrtn)$-approximation due to [Chlamt'av{c} et al APPROX '16]. This problem can also be viewed as the bipartite version of the Small Set Vertex Expansion problem (SSVE), which we call the Small Set Bipartite Vertex Expansion problem (SSBVE). SSVE, in which we are asked to find a set of k nodes to minimize their vertex expansion, has not been as well studied as its edge-based counterpart Small Set Expansion (SSE), but has recently received significant attention, e.g. [Louis-Makarychev APPROX '15]. However, due to the connection to Unique Games and hardness of approximation the focus has mostly been on sets of size $k=Omega(n)$, while we focus on the case of general $k$, for which no polylogarithmic approximation is known. We improve the upper bound for this problem by giving an $n^{1/4+varepsilon}$ approximation for SSBVE for any constant $varepsilon>0$. Our algorithm follows in the footsteps of Densest $k$-Subgraph (DkS) and related problems, by designing a tight algorithm for random models, and then extending it to give the same guarantee for arbitrary instances. Moreover, we show that this is tight under plausible complexity conjectures: it cannot be approximated better than $O(n^{1/4})$ assuming an extension of the so-called "Dense vs Random" conjecture for DkS to hypergraphs. We show that the same bound is also matched by an integrality gap for a super-constant number of rounds of the Sherali-Adams LP hierarchy, and an even worse integrality gap for the natural SDP relaxation. Finally, we design a simple bicriteria $ildeO(sqrtn)$ approximation for the more general SSVE problem.

Recommendations

• Hardness of bipartite expansion
• The small set vertex expansion problem
• Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion

Cited in

(20)

• Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
• The maximum exposure problem
• A parameterized approximation scheme for min \(k\)-cut
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• Tensor clustering with planted structures: statistical optimality and computational limits
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Pattern masking for dictionary matching: theory and practice
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• The Maximum Exposure Problem.
• The densest \(k\)-subhypergraph problem
• The small set vertex expansion problem
• Hardness of bipartite expansion
• Sherali-Adams integrality gaps matching the log-density threshold
• Min-Max Graph Partitioning and Small Set Expansion
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• scientific article; zbMATH DE number 7561533 (Why is no real title available?)
• Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion
• The small set vertex expansion problem

This page was built for publication: Minimizing the union: tight approximations for small set bipartite vertex expansion

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