Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short BroadcastsResearch Paper
A dominating set of a graph is a set of vertices such that every vertex lies in or has a neighbour in . In a distributed network the graph is also the communication medium, so an algorithm that computes must decide locally, from what the vertices can exchange in a few rounds. Approximating the minimum dominating set in a constant number of rounds…