text: We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2+e)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.
  @cite_9: For a given graph G over n vertices, let OPT"G denote the size of an optimal solution in G of a particular minimization problem (e.g., the size of a minimum vertex cover). A randomized algorithm will be called an @a-approximation algorithm with an additive error for this minimization problem if for any given additive error parameter @e>0 it computes a value [email protected]? such that, with probability at least 2 3, it holds that OPT"[email protected][email protected][email protected][email protected]@?OPT"[email protected] Assume that the maximum degree or average degree of G is bounded. In this case, we show a reduction from local distributed approximation algorithms for the vertex cover problem to sublinear approximation algorithms for this problem. This reduction can be modified easily and applied to other optimization problems that have local distributed approximation algorithms, such as the dominating set problem. We also show that for the minimum vertex cover problem, the query complexity of such approximation algorithms must grow at least linearly with the average degree [email protected]? of the graph. This lower bound holds for every multiplicative factor @a and small constant @e as long as [email protected]?=O(n @a). In particular this means that for dense graphs it is not possible to design an algorithm whose complexity is o(n).
  @cite_21: We present a technique for transforming classical approximation algorithms into constant-time algorithms that approximate the size of the optimal solution. Our technique is applicable to a certain subclass of algorithms that compute a solution in a constant number of phases. The technique is based on greedily considering local improvements in random order.The problems amenable to our technique include vertex cover, maximum matching, maximum weight matching, set cover, and minimum dominating set. For example, for maximum matching, we give the first constant-time algorithm that for the class of graphs of degree bounded by d, computes the maximum matching size to within epsivn, for any epsivn > 0, where n is the number of nodes in the graph. The running time of the algorithm is independent of n, and only depends on d and epsiv.
summary: Our centralised constant-time approximation algorithm in Theorem is based on the ideas of Parnas and Ron @cite_9 and Nguyen and Onak @cite_21 . Their work presents constant-time approximation algorithms for estimating the size of a maximal matching, maximum-cardinality matching, and maximum-weight matching. Our work complements this line of research by presenting an algorithm for estimating the size of a stable matching.