Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds

DOI10.1137/S0097539793250767zbMath0867.05063OpenAlexW1965765215MaRDI QIDQ4337636

Alessandro Panconesi, Aravind Srinivasan

Publication date: 26 May 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539793250767

zbMATH Keywords

probabilistic algorithms edge coloring correlation inequalities large deviations parallel algorithms randomized algorithms distributed algorithms stochastic dependence Chernoff-Hoeffding bounds \(\lambda\)-correlation edge-coloring problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Large deviations (60F10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items

The list chromatic number of graphs with small clique number, Distributed edge coloration for bipartite networks, An Improved Integrality Gap for Asymmetric TSP Paths, Primal Beats Dual on Online Packing LPs in the Random-Order Model, Scheduling on unrelated machines under tree-like precedence constraints, Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions, Entropy, Randomization, Derandomization, and Discrepancy, Partial Resampling to Approximate Covering Integer Programs, The game of overprescribed Cops and Robbers played on graphs, On Approximating the Stationary Distribution of Time-reversible Markov Chains, Counting colorings of triangle-free graphs, Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication, Sublinear Algorithms for Local Graph-Centrality Estimation, Stochastic packing integer programs with few queries, On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition, Better security-efficiency trade-offs in permutation-based two-party computation, Simple and fast algorithm for binary integer and online linear programming, Unnamed Item, Approximation Algorithms for Stochastic and Risk-Averse Optimization, Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs, On triangle-free list assignments, Packing list‐colorings, Limitations of current wireless link scheduling algorithms, Link scheduling in wireless sensor networks: distributed edge-coloring revisited, Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors, Maximizing coverage while ensuring fairness: a tale of conflicting objectives, A simple approach for adapting continuous load balancing processes to discrete settings, A structure theorem for almost low-degree functions on the slice, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms, Perfect matchings and Hamiltonian cycles in the preferential attachment model, Analysis of randomized protocols for conflict-free distributed access, On negative dependence properties of Latin hypercube samples and scrambled nets, Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, On approximating the stationary distribution of time-reversible Markov chains, Set families with a forbidden pattern, Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures, Approximation algorithms for time-constrained scheduling on line networks, Online Ramsey games for more than two colors, Unnamed Item, Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, Two proofs for shallow packings, Efficient distributed approximation algorithms via probabilistic tree embeddings, Superfast coloring in CONGEST via efficient color sampling, Superfast coloring in CONGEST via efficient color sampling, Sampling Lower Bounds: Boolean Average-Case and Permutations, Distributed deterministic edge coloring using bounded neighborhood independence, A constructive proof of a concentration bound for real-valued random variables, Discrepancy of high-dimensional permutations, Better streaming algorithms for the maximum coverage problem, Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem, Unnamed Item, Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations