max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 New for: D1, D2, D3, D4, D5
 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Distributed Maximum Matching in Bounded Degree Graphs Moti Medina LIAFA, Université Paris Diderot - Paris 7, Algorithms and Complexity team AG1 Mittagsseminar (own work) D1, D2, D3, D4, D5, SWS, RG1, MMCIWe use this to send out email in the morning. AG Audience English
Date: Monday, 23 February 2015 13:00 30 Minutes Saarbrücken E1 4 024
 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.
Name(s): Christina Fries --email address not disclosed on the web