Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
75
0
0.0
(
0
)
Added by
Michael Dinitz
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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(sqrt{n})$-approximation due to [Chlamtav{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 $tilde O(sqrt{n})$ approximation for the more general SSVE problem.
rate research
Read More
We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges $E$ with arbitrary covering requirements $k_e$, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge $e$ is considered covered by the first time when $k_e$ many of its vertices appear in the ordering. We give a $4.642$ approximation algorithm for GMSSC, coming close to the best possible bound of $4$, already for the classical special case (with all $k_e=1$) of min sum set cover (MSSC) studied by Feige, Lov{a}sz and Tetali, and improving upon the previous best known bound of $12.4$ due to Im, Sviridenko and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based $4$ approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph and $k_e = 1$, for every edge. We give a $16/9$ approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best $1.999946$ approximation of Barenholz, Feige and Peleg. (The claimed $1.79$ approximation result of Iwata, Tetali and Tripathi for the MSVC turned out have an unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and consider the $ell_p$ norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of $(p+1)^{1+1/p}$, for all $pge 1$. For $p=1$, this gives yet another proof of the $4$ approximation for MSSC.
We establish a bound for the classic PUSH-PULL rumor spreading protocol on arbitrary graphs, in terms of the vertex expansion of the graph. We show that O(log^2(n)/alpha) rounds suffice with high probability to spread a rumor from a single node to all n nodes, in any graph with vertex expansion at least alpha. This bound matches the known lower bound, and settles the question on the relationship between rumor spreading and vertex expansion asked by Chierichetti, Lattanzi, and Panconesi (SODA 2010). Further, some of the arguments used in the proof may be of independent interest, as they give new insights, for example, on how to choose a small set of nodes in which to plant the rumor initially, to guarantee fast rumor spreading.
We give efficient distributed algorithms for the minimum vertex cover problem in bipartite graphs in the CONGEST model. From KH{o}nigs theorem, it is well known that in bipartite graphs the size of a minimum vertex cover is equal to the size of a maximum matching. We first show that together with an existing $O(nlog n)$-round algorithm for computing a maximum matching, the constructive proof of KH{o}nigs theorem directly leads to a deterministic $O(nlog n)$-round CONGEST algorithm for computing a minimum vertex cover. We then show that by adapting the construction, we can also convert an emph{approximate} maximum matching into an emph{approximate} minimum vertex cover. Given a $(1-delta)$-approximate matching for some $delta>1$, we show that a $(1+O(delta))$-approximate vertex cover can be computed in time $O(D+mathrm{poly}(frac{log n}{delta}))$, where $D$ is the diameter of the graph. When combining with known graph clustering techniques, for any $varepsilonin(0,1]$, this leads to a $mathrm{poly}(frac{log n}{varepsilon})$-time deterministic and also to a slightly faster and simpler randomized $O(frac{log n}{varepsilon^3})$-round CONGEST algorithm for computing a $(1+varepsilon)$-approximate vertex cover in bipartite graphs. For constant $varepsilon$, the randomized time complexity matches the $Omega(log n)$ lower bound for computing a $(1+varepsilon)$-approximate vertex cover in bipartite graphs even in the LOCAL model. Our results are also in contrast to the situation in general graphs, where it is known that computing an optimal vertex cover requires $tilde{Omega}(n^2)$ rounds in the CONGEST model and where it is not even known how to compute any $(2-varepsilon)$-approximation in time $o(n^2)$.
We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists a subset F of V, of size at most k, such that G[V F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time $O(2^{O(k)}n^{O(1)})$ on general graphs and in time $O(2^{O(sqrt{k}log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses as subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it will be useful for obtaining parameterized algorithms for other connectivity problems.
In a multiparty message-passing model of communication, there are $k$ players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work cite{phillips12,woodruff12,woodruff13}, strong lower bounds of the form $Omega(n cdot k)$ were obtained for several functions in the message-passing model; however, a lower bound on the classical Set Disjointness problem remained elusive. In this paper, we prove tight lower bounds of the form $Omega(n cdot k)$ for the Set Disjointness problem in the message passing model. Our bounds are obtained by developing information complexity tools in the message-passing model, and then proving an information complexity lower bound for Set Disjointness. As a corollary, we show a tight lower bound for the task allocation problem cite{DruckerKuhnOshman} via a reduction from Set Disjointness.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
