Distributed balanced color assignment on arbitrary networks

DOI10.1016/J.TCS.2019.12.023MaRDI QIDQ2290638zbMATH OpenOpenAlexWikidataFDO

Authors Gianluca De Marco, Mauro Leoncini, Manuela Montangero

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.12.023

zbMATH Keywords

assignment problemsdistributed algorithmsdistributed computing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Analysis of algorithms (68W40) Discrete location and assignment (90B80)

Review text

A generalized bipartite matching problem is studied, the balanced color assignment problem: a set of \(n\) agents hold items of \(m\) possible colors and they are connected by an asynchronous arbitrary communication network and have to distributively find a repartition of the colors such that the amount of colors for each agent is as balanced as possible. In particular, a lower bound is proposed on the message complexity of the balanced color assignment problem that holds even for approximate solutions. The authors propose a novel polynomial-time distributed algorithm designed to run on an arbitrary network with the agents as nodes. The efficiency in terms of time and complexity is proved for large diameter graphs.

Recommendations

• Locally optimal load balancing
• Distributed Selfish Load Balancing
• Perfectly balanced allocation
• On the complexity of distributed graph coloring
• The communication complexity of distributed task allocation

Cites work

• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A new distributed algorithm to find breadth first search trees
• Distributed balanced color assignment on arbitrary networks
• Distributed Computing: A Locality-Sensitive Approach
• Network flows. Theory, algorithms, and applications.
• The -assignment problems

Cited in

(2)

• Distributed balanced color assignment on arbitrary networks
• scientific article; zbMATH DE number 1750105 (Why is no real title available?)

This page was built for publication: Distributed balanced color assignment on arbitrary networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290638)