A Distributed Minimum Cut Approximation Scheme

2014/01/21 by Su, Hsin-Hao
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1401.5316

Abstract

In this paper, we study the problem of approximating the minimum cut in a distributed message-passing model, the CONGEST model. The minimum cut problem has been well-studied in the context of centralized algorithms. However, there were no known non-trivial algorithms in the distributed model until the recent work of Ghaffari and Kuhn. They gave algorithms for finding cuts of size O(ε^-1λ) and (2+ε)λ in O(D)+O(n^1/2+ε) rounds and O(D+√(n)) rounds respectively, where λ is the size of the minimum cut. This matches the lower bound they provided up to a polylogarithmic factor. Yet, no scheme that achieves (1+ε)-approximation ratio is known. We give a distributed algorithm that finds a cut of size (1+ε)λ in O(D+√(n)) time, which is optimal up to polylogarithmic factors.

Related

• Almost-Tight Distributed Minimum Cut Algorithms
• Distributed Minimum Cut Approximation
• Brief Announcement: Almost-Tight Approximation Distributed Algorithm for\n Minimum Cut
• Fast Distributed Approximation for Max-Cut
• Approximation of Distances and Shortest Paths in the Broadcast Congest\n Clique