MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Distributed Maximum Matching in Bounded Degree Graphs

Moti Medina
Université Paris Diderot
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 10 March 2015
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

We present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted case computes a matching whose size is at least $(1-\eps)$ times the optimal in$\Delta^{O(1/\eps)} + O\left(\frac{1}{\eps^2}\right) \cdot\log^*(n)$ rounds where $n$ is the number of vertices in the graph and $\Delta$ is the maximum degree. Our algorithm for the edge-weighted case computes a matching whose weight is at least $(1-\eps)$ times the optimal in$\log(\min\{1/\wmin,n/\eps\})^{O(1/\eps)}\cdot(\Delta^{O(1/\eps)}+\log^*(n))$ rounds for edge-weights in $[\wmin,1]$.
The best previous algorithms for both the unweighted case and the weighted case are by Lotker, Patt-Shamir, and Pettie~(SPAA 2008). For the unweighted case they give a randomized $(1-\eps)$-approximation algorithm that runs in $O((\log(n)) /\eps^3)$ rounds. For the weighted case they give a randomized $(1/2-\eps)$-approximation algorithm that runs in $O(\log(\eps^{-1}) \cdot \log(n))$ rounds. Hence, our results improve on the previous ones when the parameters Δ, $\eps$ and $\wmin$ are constants (where we reduce the number of runs from O(log(n)) to O(log∗(n))), and more generally when Δ, $1/\eps$ and $1/\wmin$ are sufficiently slowly increasing functions of n. Moreover, our algorithms are deterministic rather than randomized.

Contact

Christina Fries
--email hidden
passcode not visible
logged in users only

Christina Fries, 02/26/2015 01:58 PM -- Created document.