Abstract
Local computation algorithms (LCAs) produce small parts of a single (possibly approximate) solution to a given search problem using time and space sublinear in the size of the input. In this work we present LCAs whose time complexity (and usually also space complexity) is independent of the input size. Specifically, we give (1) a (1 − 𝜖)-approximation LCA to the maximum weight acyclic edge set, (2) LCAs for approximating multicut and integer multicommodity flow on trees, and (3) a local reduction of weighted matching to any unweighted matching LCA, such that the running time of the weighted matching LCA is d times (where d is the maximal degree) the running time of the unweighted matching LCA, (and therefore independent of the edge weight function).
Similar content being viewed by others
Notes
We assume the standard uniform-cost RAM model [1], in which the word size is O(log n) bits, where n is the input size.
We typically assume that vertex degrees are bounded by a constant.
In the LOCAL model [19], at the beginning of the algorithm’s execution, each vertex knows only its ID and the IDs of its neighbors. In each round, each vertex is allowed to send an unbounded message to all of its neighbors and perform an unbounded amount of computation. The goal is to minimize the maximal number of rounds a vertex requires to compute its own portion of the output.
We note that while our algorithm for MWM runs in constant time, independently of the size of the graph and of the edge weights, its approximation guarantee is much worse than that of [4], whose approximation factor is (1 − 𝜖).
In case of a randomized algorithm, expectation is over its random choices.
Note that the LCA is not allowed to deviate from the enduring memory bound.
Algorithm 6 inherits it running time, space complexity and failure probability from theLCA it uses as a subroutine.
In order to simulate Algorithm 1 on a vertex at distance i from v for j rounds, we need to discover vertices at distance i + j from v.
Technically, this is a global algorithm, which we later show how to implement as an LCA.
The ratio is \(\frac 14\) when all capacities are even, and it tends to \(\frac 14\) as c min → ∞. For c min = 1 the approximation ratio is 0.
References
Aho, A.V., Hopcroft, J.E.: The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston (1974)
Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1132–1139 (2012)
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control. 70(1), 32–53 (1986)
Even, G., Medina, M., Ron, D.: Deterministic stateless centralized local algorithms for bounded degree graphs. In: 22th Annual European Symposium on Algorithms (ESA), pp. 394–405 (2014)
Göös, M., Hirvonen, J., Levi, R., Medina, M., Suomela, J.: Non-local probes do not help with many graph problems. In: 30th International Symposium, on Distributed Computing (DISC), pp. 201–214 (2016)
Garg, N., Vazirani, V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)
Göös, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 175–184 (2012)
Kuhn, F.: Local approximation of covering and packing problems. In: Encyclopedia of Algorithms (2008)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceedings of the 17Th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 980–989 (2006)
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1) (1992)
Lotker, Z., Patt-Shamir, B., Rosén, A.: Distributed approximate matching. SIAM J. Comput. 39(2) (2009)
Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. In: Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP), pp. 653–664 (2012)
Mansour, Y., Vardi, S.: A Local computation approximation scheme to maximum matching. In: APPROX-RANDOM, pp. 260–273 (2013)
Naor, M., Stockmeyer, L.J.: What can be computed locally? SIAM J. Comput. 24(6), 1259–1277 (1995)
Nešetřil, J., Milková, E., Nešetřilová, H.: Otakar Borůvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history. Discret. Math. 233(1), 3–36 (2001)
Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 327–336 (2008)
Oxley, J.: Matroid Theory. Oxford University Press (1992)
Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97–100 (2001)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)
Reingold, O., Vardi, S.: New techniques and tighter bounds for local computation algorithms. J. Comput. Syst. Sci. 82(7), 1180–1200 (2016)
Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS), pp. 223–238 (2011)
Suomela, J.: Survey of local algorithms. ACM Comput. Surv. 45(2), 24 (2013)
Tarjan, R.E.: Data structures and network algorithms. Society for industrial and applied mathematics, Philadelphia (1983)
Uehara, R., Chen, Z.: Parallel approximation algorithms for maximum weighted matching in general graphs. In: Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, International Conference IFIP TCS, pp. 84–98 (2000)
Vardi, S.: Designing Local Computation Algorithms and Mechanisms. PhD Thesis. Tel Aviv University, Tel Aviv (2015)
Vazirani, V.V.: Approximation algorithms. Springer (2001)
Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: DISC, pp. 335–348 (2004)
Acknowledgements
The authors would like to thank the anonymous reviewers for their useful feedback.
Yishay Mansour is supported in part by a grant from the Israel Science Foundation, by a grant from United States-Israel Binational Science Foundation (BSF), by a grant from the Israeli Ministry of Science (MoS) and the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Boaz Patt-Shamir is supported in part by the Israel Science Foundation (grant No. 1444/14) and by the Israel Ministry of Science and Technology. Shai Vardi is supported in part by the Google Europe Fellowship in Game Theory.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mansour, Y., Patt-Shamir, B. & Vardi, S. Constant-Time Local Computation Algorithms. Theory Comput Syst 62, 249–267 (2018). https://doi.org/10.1007/s00224-017-9788-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-017-9788-3