Distributed approximation graph algorithms
In distributed graph models, each node of the input graph is a processor that has communication ports to its neighboring nodes. In synchronous rounds, the nodes can transmit messages to their neighbors and perform arbitrary amount of computation. The time complexity of the protocol is the maximum over all nodes of the number of rounds used by a node. In the LOCAL model, nodes can transmit messages of arbitrary length in each round, while in the CONGEST model, the messages must be O(log n) bits, where n is the number of nodes in the network. In the Broadcast-CONGEST model, each node transmits a single message to all its neighbors in a round (but can receive different messages), while in CONGEST and LOCAL, the messages to the neighbors can be all different. We study approximation algorithms for problems on graphs (e.g., Maximum Independent Set) in a distributed setting.