Learning-augmented online algorithms for bipartite matching and other combinatorial problems

The research pursued for the thesis will study the design and analysis of learning augmented algorithms for bipartite matching problems and other online problems.

Learning augmented algorithms are algorithms that receive some form of prediction or advice in addition to the problem input, and the aim is to design algorithms that perform provably well if the predictions are correct but whose performance doesn't deteriorate too much even if the predictions are arbitrarily wrong.

The research project will use techniques from theoretical computer science and mathematics such as competitive analysis of online algorithms (comparing the solution computed by the algorithm to the best possible solution that could have been found if full information has been given in advance) and adversarial lower bound constructions to obtain theoretical results.

Applications of online matching problems that motivate this research arise in scenarios where entities of two groups must be assigned to each other, with one group being known in advance and the members of the other group arriving over time (for example, matching refugees to host families).