Converting online algorithms to local computation algorithms Conference

Mansour, Y, Rubinstein, A, Vardi, S et al. (2012). Converting online algorithms to local computation algorithms . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 7391 LNCS(PART 1), 653-664. 10.1007/978-3-642-31594-7_55

cited authors

  • Mansour, Y; Rubinstein, A; Vardi, S; Xie, N

authors

abstract

  • We propose a general method for converting online algorithms to local computation algorithms, by selecting a random permutation of the input, and simulating running the online algorithm. We bound the number of steps of the algorithm using a query tree, which models the dependencies between queries. We improve previous analyses of query trees on graphs of bounded degree, and extend this improved analysis to the cases where the degrees are distributed binomially, and to a special case of bipartite graphs. Using this method, we give a local computation algorithm for maximal matching in graphs of bounded degree, which runs in time and space O(log3 n). We also show how to convert a large family of load balancing algorithms (related to balls and bins problems) to local computation algorithms. This gives several local load balancing algorithms which achieve the same approximation ratios as the online algorithms, but run in O(logn) time and space. Finally, we modify existing local computation algorithms for hypergraph 2-coloring and k-CNF and use our improved analysis to obtain better time and space bounds, of O(log4 n), removing the dependency on the maximal degree of the graph from the exponent. © 2012 Springer-Verlag.

publication date

  • December 1, 2012

published in

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 13

start page

  • 653

end page

  • 664

volume

  • 7391 LNCS

issue

  • PART 1