Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, March 08, 2022, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Julian Portmann

Average Awake Complexity of MIS and Matching

Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the notion of awake complexity for distributed algorithms, which measures the number of rounds in which a node is awake. In the other rounds, the node is sleeping and performs no computation or communication. Measuring the number of awake rounds can be of significance in many settings of distributed computing, e.g., in sensor networks where energy consumption is of concern. In that paper, Chatterjee et al. provide an elegant randomized algorithm for the Maximal Independent Set (MIS) problem that achieves an O(1) node-averaged awake complexity. That is, the average awake time among the nodes is O(1) rounds. However, to achieve that, the algorithm sacrifices the more standard round complexity measure from the well-known O(log n) bound of MIS, due to Luby [STOC'85], to O(log^{3.41} n) rounds. Our first contribution is to present a simple randomized distributed MIS algorithm that, with high probability, has O(1) node-averaged awake complexity and O(log n) worst-case round complexity. Our second, and more technical contribution, is to show algorithms with the same O(1) node-averaged awake complexity and O(log n) worst-case round complexity for 1+Ɛ approximation of maximum matching and 2+Ɛ approximation of minimum vertex cover, where Ɛ denotes an arbitrary small positive constant. In this talk I will focus on how to turn an algorithm that computes a constant approximation for maximum matching into an 1+Ɛ approximation algorithm. This is joint work with Mohsen Ghaffari.

Information for students and suggested topics for student talks