ﻻ يوجد ملخص باللغة العربية
We study vertex cut and flow sparsifiers that were recently introduced by Moitra, and Leighton and Moitra. We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log^2 k / log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomial-time algorithm for finding optimal operators. We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1930s. Using this connection, we prove a lower bound of Omega(sqrt{log k/log log k}) for flow sparsifiers and a lower bound of Omega(sqrt{log k}/log log k) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist tilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than tilde Omega(sqrt{log k}) would imply a negative answer to this question.
Let $G$ be a graph and $S, T subseteq V(G)$ be (possibly overlapping) sets of terminals, $|S|=|T|=k$. We are interested in computing a vertex sparsifier for terminal cuts in $G$, i.e., a graph $H$ on a smallest possible number of vertices, where $S c
We construct a regular random projection of a metric space onto a closed doubling subset and use it to linearly extend Lipschitz and $C^1$ functions. This way we prove more directly a result by Lee and Naor and we generalize the $C^1$ extension theorem by Whitney to Banach spaces.
We study distributed algorithms built around edge contraction based vertex sparsifiers, and give sublinear round algorithms in the $textsf{CONGEST}$ model for exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on spar
Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cut structure has been extensively studied and has many applications. In
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bou