Please use this identifier to cite or link to this item:
Title: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds
Authors: Panconesi, A.
Srinivasan, A. 
Keywords: λ-correlation
Chernoff-Hoeffding bounds
Correlation inequalities
Distributed algorithms
Edge coloring
Large deviations
Parallel algorithms
Probabilistic algorithms
Stochastic dependence
Issue Date: Apr-1997
Citation: Panconesi, A.,Srinivasan, A. (1997-04). Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM Journal on Computing 26 (2) : 350-368. ScholarBank@NUS Repository.
Abstract: Certain types of routing, scheduling, and resource-allocation problems in a distributed setting can be modeled as edge-coloring problems. We present fast and simple randomized algorithms for edge coloring a graph in the synchronous distributed point-to-point model of computation. Our algorithms compute an edge coloring of a graph G with n nodes and maximum degree A with at most 1.6Δ + O(log1+δ n) colors with high probability (arbitrarily close to 1) for any fixed δ > 0; they run in polylogarithmic time. The upper bound on the number of colors improves upon the (2Δ - 1)-coloring achievable by a simple reduction to vertex coloring. To analyze the performance of our algorithms, we introduce new techniques for proving upper bounds on the tail probabilities of certain random variables. The Chernoff-Hoeffding bounds are fundamental tools that are used very frequently in estimating tail probabilities. However, they assume stochastic independence among certain random variables, which may not always hold. Our results extend the Chernoff-Hoeffding bounds to certain types of random variables which are not stochastically independent. We believe that these results are of independent interest and merit further study.
Source Title: SIAM Journal on Computing
ISSN: 00975397
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on May 12, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.