Online Algorithms for Matching and Coloring Problems
Event details
| Date | 21.06.2023 |
| Hour | 15:30 › 17:30 |
| Speaker | Radu Vintan |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Ola Svensson
Co-examiner: Prof. Mika Göös
Abstract
In the broad field of online algorithms, two related and especially important problems are online matching and online edge coloring. The first problem has been studied intensively since it was introduced by Karp et al. in 1990. This initial paper provided an (optimal) (1-1/e)-competitive algorithm for one-sided vertex arrivals. General vertex arrival and edge arrival settings are also well understood; most recent research therefore goes into studying more restrictive arrival models, such as random-order arrival, or more particular graph configurations, such as d-regular bipartite graphs.
The second problem was introduced by Bar-Noy et al. for adversarial edge arrivals. They conjectured that a (1+o(1))-competitive edge coloring algorithm exists in the regime where the maximum degree Delta = omega(log n) is given to the algorithm before any input arrives. This conjecture has been solved in less restrictive arrival models, but for edge arrivals it remains open. The literature contains a particularly important reduction from online edge coloring to a strengthened version of online matching: An online matching algorithm which matches every edge with probability 1/(alpha Delta) can be converted into an alpha-competitive online coloring algorithm. This reduction has been used by Tarnawski et al. in 2022 to obtain the state-of-the-art result: an e/(e-1)-competitive algorithm.
A first research direction is to solve the conjecture by Bar-Noy et al. using the reduction and in particular to improve the previously mentioned result. In fact, me and my coauthors believe to already have reached this goal. Our algorithm is relatively simple and intuitive. Crucially and in contrast to previous papers, our analysis avoids dealing with hard to bound correlations. However, in their original paper, Bar-Noy et al. suggested an even simpler algorithm, for which the conjecture is still open. We plan to investigate this in the future. Another promising research direction is to investigate both lower and upper bounds for deterministic online edge coloring algorithms in the Delta = omega(log n) regime. Surprisingly, there are no known non-trivial results. In particular, it is not clear in this setting if any deterministic algorithm performs better than the trivial greedy algorithm which uses (in the worst-case) 2Delta - 1 colors. On the opposite side, the conjecture by Bar-Noy et al. has not been disproven even for deterministic algorithms, and it is in principle possible that such an algorithm achieves (1 + o(1))-competitiveness.
My long-term research plans consist not only in studying the previously two outlined directions, but more generally in trying to improve the state-of-the-art relating to online matching/coloring and/or other important online and approximation problems in the field of discrete optimization.
Background papers
[1] Online Edge Coloring via Tree Recurrences and Correlation Decay (STOC 2022) by Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney and Jakub Tarnawsk ihttps://arxiv.org/pdf/2111.00721.pdf
[2] Randomized Online Matching in Regular Graphs (SODA 2018 by Ilan Reuven Cohen and David Wajc https://www.cs.cmu.edu/~dwajc/pdfs/cohen18.pdf
[3] Randomized primal-dual analysis of RANKING for online bipartite matching (SODA 2013) by Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg https://www.cs.cornell.edu/courses/cs6820/2012fa/handouts/djk.pdf
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Ola Svensson
Co-examiner: Prof. Mika Göös
Abstract
In the broad field of online algorithms, two related and especially important problems are online matching and online edge coloring. The first problem has been studied intensively since it was introduced by Karp et al. in 1990. This initial paper provided an (optimal) (1-1/e)-competitive algorithm for one-sided vertex arrivals. General vertex arrival and edge arrival settings are also well understood; most recent research therefore goes into studying more restrictive arrival models, such as random-order arrival, or more particular graph configurations, such as d-regular bipartite graphs.
The second problem was introduced by Bar-Noy et al. for adversarial edge arrivals. They conjectured that a (1+o(1))-competitive edge coloring algorithm exists in the regime where the maximum degree Delta = omega(log n) is given to the algorithm before any input arrives. This conjecture has been solved in less restrictive arrival models, but for edge arrivals it remains open. The literature contains a particularly important reduction from online edge coloring to a strengthened version of online matching: An online matching algorithm which matches every edge with probability 1/(alpha Delta) can be converted into an alpha-competitive online coloring algorithm. This reduction has been used by Tarnawski et al. in 2022 to obtain the state-of-the-art result: an e/(e-1)-competitive algorithm.
A first research direction is to solve the conjecture by Bar-Noy et al. using the reduction and in particular to improve the previously mentioned result. In fact, me and my coauthors believe to already have reached this goal. Our algorithm is relatively simple and intuitive. Crucially and in contrast to previous papers, our analysis avoids dealing with hard to bound correlations. However, in their original paper, Bar-Noy et al. suggested an even simpler algorithm, for which the conjecture is still open. We plan to investigate this in the future. Another promising research direction is to investigate both lower and upper bounds for deterministic online edge coloring algorithms in the Delta = omega(log n) regime. Surprisingly, there are no known non-trivial results. In particular, it is not clear in this setting if any deterministic algorithm performs better than the trivial greedy algorithm which uses (in the worst-case) 2Delta - 1 colors. On the opposite side, the conjecture by Bar-Noy et al. has not been disproven even for deterministic algorithms, and it is in principle possible that such an algorithm achieves (1 + o(1))-competitiveness.
My long-term research plans consist not only in studying the previously two outlined directions, but more generally in trying to improve the state-of-the-art relating to online matching/coloring and/or other important online and approximation problems in the field of discrete optimization.
Background papers
[1] Online Edge Coloring via Tree Recurrences and Correlation Decay (STOC 2022) by Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney and Jakub Tarnawsk ihttps://arxiv.org/pdf/2111.00721.pdf
[2] Randomized Online Matching in Regular Graphs (SODA 2018 by Ilan Reuven Cohen and David Wajc https://www.cs.cmu.edu/~dwajc/pdfs/cohen18.pdf
[3] Randomized primal-dual analysis of RANKING for online bipartite matching (SODA 2013) by Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg https://www.cs.cornell.edu/courses/cs6820/2012fa/handouts/djk.pdf
Practical information
- General public
- Free