max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | Distributed Maximum Matching in Bounded Degree Graphs |
---|---|

Speaker: | Moti Medina |

coming from: | Université Paris Diderot |

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1, D2, D3, D4, D5, SWS, RG1, MMCI We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Tuesday, 10 March 2015 |
---|---|

Time: | 13:00 |

Duration: | 30 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 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 |
---|

Video Broadcast: | No | To Location: |
---|

Note: | |
---|---|

Attachments, File(s): |

Created: | Christina Fries/AG1/MPII/DE, 02/26/2015 01:56 PM | Last modified: | Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM |

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