BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Memento EPFL// BEGIN:VEVENT SUMMARY:Online Algorithms for Matching and Coloring Problems DTSTART:20230621T153000 DTEND:20230621T173000 DTSTAMP:20260407T064315Z UID:0fcce78b6f8cb858280a41aeb25698c4b345b14567b2e3e3316bb0c0 CATEGORIES:Conferences - Seminars DESCRIPTION:Radu Vintan\nEDIC candidacy exam\nExam president: Prof. Friedr ich Eisenbrand\nThesis advisor: Prof. Ola Svensson\nCo-examiner: Prof. Mik a Göös\n\nAbstract\nIn the broad field of online algorithms\, two relate d and especially important problems are online matching and online edge co loring. The first problem has been studied intensively since it was introd uced by Karp et al. in 1990. This initial paper provided an (optimal) (1-1 /e)-competitive algorithm for one-sided vertex arrivals. General vertex ar rival and edge arrival settings are also well understood\; most recent res earch therefore goes into studying more restrictive arrival models\, such as random-order arrival\, or more particular graph configurations\, such a s d-regular bipartite graphs.\n\nThe 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 maximu m degree Delta = omega(log n) is given to the algorithm before any input a rrives. This conjecture has been solved in less restrictive arrival models \, but for edge arrivals it remains open. The literature contains a partic ularly important reduction from online edge coloring to a strengthened ver sion of online matching: An online matching algorithm which matches every edge with probability 1/(alpha Delta) can be converted into an alpha-compe titive online coloring algorithm. This reduction has been used by Tarnawsk i et al. in 2022 to obtain the state-of-the-art result: an e/(e-1)-competi tive algorithm.\n\nA first research direction is to solve the conjecture b y Bar-Noy et al. using the reduction and in particular to improve the prev iously 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 promisin g research direction is to investigate both lower and upper bounds for det erministic online edge coloring algorithms in the Delta = omega(log n) reg ime. 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) 2D elta - 1 colors. On the opposite side\, the conjecture by Bar-Noy et al. h as not been disproven even for deterministic algorithms\, and it is in pri nciple possible that such an algorithm achieves (1 + o(1))-competitiveness .\n\nMy long-term research plans consist not only in studying the previous ly two outlined directions\, but more generally in trying to improve the s tate-of-the-art relating to online matching/coloring and/or other importan t online and approximation problems in the field of discrete optimization. \n\nBackground papers\n[1] Online Edge Coloring via Tree Recurrences and C orrelation Decay (STOC 2022) by Janardhan Kulkarni\, Yang P. Liu\, Ashwin Sah\, Mehtaab Sawhney and Jakub Tarnawsk ihttps://arxiv.org/pdf/2111.00721 .pdf\n \n[2] Randomized Online Matching in Regular Graphs (SODA 2018 by I lan Reuven Cohen and David Wajc https://www.cs.cmu.edu/~dwajc/pdfs/cohen18 .pdf\n \n[3] Randomized primal-dual analysis of RANKING for online bipart ite matching (SODA 2013) by Nikhil R. Devanur\, Kamal Jain\, and Robert D. Kleinberg https://www.cs.cornell.edu/courses/cs6820/2012fa/handouts/djk.p df\n\n\n  LOCATION:BC 333 https://plan.epfl.ch/?room==BC%20333 STATUS:CONFIRMED END:VEVENT END:VCALENDAR