Fast primal-dual distributed algorithms for scheduling and matching problems

摘要

In this paper we give efficient distributed algorithms computing approximate solutions to general scheduling and matching problems. All approximation guarantees are within a constant factor of the optimum. By "efficient", we mean that the number of communication rounds is poly-logarithmic in the size of the input. In the scheduling problem, we have a bipartite graph with computing agents on one side and resources on the other. Agents that share a resource can communicate in one time step. Each agent has a list of jobs, each with its own length and profit, to be executed on a neighbouring resource within a given time-window. Each job is also associated with a rational number in the range between zero and one (width), specifying the amount of resource required by the job. Resources can execute non preemptively multiple jobs whose total width at any given time is at most one. The goal is to maximize the profit of the jobs that are scheduled. We then adapt our algorithm for scheduling, to solve the weighted b-matching problem, which is the generalization of the weighted matching problem where for each vertex v, at most b(v) edges incident to v, can be included in the matching. For this problem we obtain a randomized distributed algorithm with approximation guarantee of 1/(6+∈), for any ∈ > 0. For weighted matching, we devise arndeterministic distributed algorithm with the same approximation ratio. To our knowledge, we give the first distributed algorithm for the aforementioned scheduling problem as well as the first deterministic distributed algorithm for weighted matching with poly-logaritmic running time. A very interesting feature of our algorithms is that they are all derived in a systematic manner from primal-dual algorithms.