In this article, we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read-only input) is sublinear in the number of edges m and the access to input is constrained. These questions arise in many natural settings, and in particular in the analysis of streaming algorithms, MapReduce or similar algorithms, or message passing distributed computing that model constrained parallelism with sublinear central processing. We focus on weighted nonbipartite maximum matching in this article. For any constant p > 1, we provide an iterative sampling-based algorithm for computing a (1 − ϵ )-approximation of the weighted nonbipartite maximum matching that uses O (p/ϵ ) rounds of sampling, and O (n 1+1/p ) space. The results extend to b-Matching with small changes. This article combines adaptive sketching literature and fast primal-dual algorithms based on relaxed Dantzig-Wolfe decision procedures. Each round of sampling is implemented through linear sketches and can be executed in a single round of streaming or two rounds of MapReduce. The article also proves that nonstandard linear relaxations of a problem, in particular penalty-based formulations, are helpful in reducing the adaptive dependence of the iterations. subsequent iterations. The computation at a particular round depends on the computation in previous rounds and thus the algorithms are adaptive. The existence of such constant round iterative near-optimal algorithms is typically not known for many combinatorial optimization problems. We note that many of these distributed iterative computing environments, for example, streaming, MapReduce and its variants, and message passing distributed algorithms, differ considerably in their details. While most algorithms focus on specific models, larger abstractions that span multiple models are not readily available. In the context of this article, we use the fact that environments that are widely adopted typically allow sampling and computation of inner products with pseudorandom vectors (linear sketches). Furthermore, the considerations of computational environments under specific resource constraints such as communication, space, or access to data have not been widely addressed in modeling combinatorial optimization problems. We are often left with formulations that were designed for a different computational environment in mind. Nonbipartite matching has long been a standard bearer of combinatorial optimization problems. In this article, we focus on weighted nonbipartite maximum b-matching problems and devise new relaxations that are useful for resource-constrained models. At a high level, our algorithm can be viewed as a recursive sampling algorithm. In each iteration, we redefine the weights of the datapoints using functions that are efficient to represent, communicate, and compute. On a more technical level, we use inner-product-based sampling so that we can reduce the adaptivity of the algorithm, and thereby the number of iterations in comparison to standard iterative approaches for solving these problems. A sampling-based algorithm for finding the edges in a maximum matching is natural and intuitive: we iteratively sample edges; we show that the sampled edges contain a large matching or we refine the weights and repeat. While the high-level description is natural, the details of the analysis, for example, the demonstration of a large matching or refinements of weights, are nonobvious at best. In a recent result (Lattanzi et al. 2011) , it was shown that for an n node m edge graph, we can find an O (1) approximation for bipartite graphs using O (p) rounds of edge filtering via mapreduce and O (n 1+1/p ) centralized space (for any constant p > 1). However, it was also shown that the approximation bound achieved in the actual implementation was better than the worst case. This raises the natural question: is a (1 − ϵ )-approximation for any constant ϵ > 0 achievable in a small number of rounds? In this article, we provide such an algorithm. Note that although we discuss matchings, these questions are applicable to a broader set of problems; in many scenarios, iterative algorithms converge faster and better than deemed by the worst-case guarantees. Unfortunately, there are few systematic techniques that allow us to analyze iterative algorithms. One well-known example is linear (or convex) programming-and for maximum weighted matching there are LP relaxations that are exact. Therefore, any algorithm that provides a (1 − ϵ ) approximation must also (possibly implicitly) provide a bound for the underlying LP, which is provided in Definition 1. In this simple example, we can set z U = 10ϵ and x i = 1 − 10ϵ for the vertex at the apex. It is unclear if such reassignments exist in a large graph. And even for unweighted graphs, note that n 1/δ different z U affect a single edge and the width is large. Viewed another way, if a problem definition requires a constraint matrix of size n 1/ϵ × m and we wish to solve that problem in o(m, n 1/ϵ ) space and constant number of rounds, then simple transformations will not suffice and newer ideas are necessary. Matching has been well studied in the context of streaming algorithms. In such a setting, the input corresponds to a sequence of edges and associated weights (i, j, w i j ), in arbitrary order, and the random access memory (RAM) is sublinear in the input size. The computation proceeds in passes. The algorithm is typically measured on how close is the output solution to the optimum solution (its approximation ratio), the amount of memory, and the number of passes-smaller is more desirable in all these measures. Observe that iterative sampling or sketching is easy to compute in the streaming model. For weighted nonbipartite matching, no previous result was known in the streaming model where the number of iterations is independent of the problem parameters. For unweighted cardinality matching, McGregor (2005) provided an algorithm with 2 O (1/ϵ ) iterations usingÕ (n) space (where we ignore polylogarithmic factors and polynomial dependence on 1/ϵ) in this model. The best-known single-round results that actually produce a matching are an O (1) approximation using a single round (Eggert et al. 2009; Epstein et al. 2010; Feigenbaum et al. 2005; Zelke 2008) , which applies to both bipartite and nonbipartite graphs. For bipartite graphs a (1 − ϵ )-approximation in O (ϵ −2 log 1 ϵ ) rounds (Ahn and Guha 2013) and a (1 − ϵ ) approximation in O (ϵ −2 ) rounds in a vertex arrival model (assuming order on the list of input edges) (Kapralov 2013) were known. In Guruswami and Onak (2013) , it is shown that a space bound of n 1+Ω(1/p ) /p O (1) is necessary for a p round communication protocol to find the exact maximum in bipartite graphs. Another well-studied model is the map-reduce model with some centralized storage. The computation proceeds by applying the map and reduce operators to the arbitrary order of the edges. The map operation is a uniform operation that is applied to all edges to partition them. The reduce operator applies to each partition and produces a small amount of information, which is sent back to the central coordinator (see Lattanzi et al. (2011) and references therein). Iterative sampling or sketching is not difficult to achieve in this model. The approximation for bipartite/nonbipartite graphs using O (p) rounds of sampling andÕ (n 1+1/p ) space in Lattanzi et al. (2011) corresponds to iterative sampling (and filtering). For bipartite graphs, (1 − ϵ ) approximation is achievable using several algorithms (see Bahmani et al. (2014) ), but they require Ω(log n) rounds. Matching has also been studied in the context of distributed computing (see Mansour and Vardi (2013) for a survey of results). The congested clique model (Drucker et al. 2014) is of interest to this article; in that model, n participants have local (possibly shared inputs) and any node can send a bounded-length message to any other node in a round. The results in this article are as follows: (i) a result on space efficient computation of matchings (ii) a refinement of the notion of adaptivity into "adaptivity at sampling" and "adaptivity at use,"
Similarly, Ahn and Guha REF build on the filtering approach of Lattanzi et al. and design a primal-dual method for computing a (1+ ϵ)-approximate weighted maximum matching.
Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
TOPC
Mathematics Computer Science