On-line algorithms with random order
In the online model of computation, the input is not given all at once but is revealed gradually over time, in a sequential manner. The algorithm must maintain at all times a solution for the input seen so far, and its decisions are usually irrevocable. This setting can be interpreted as a game played between an on-line algorithm and an adversary generating the input sequence. Motivated by the observation that the input items often come from diverse uncoordinated and unsynchronized sources, the random order model assumes that the adversary chooses an arbitrary instance, but its elements are presented to the algorithm in uniform random order. Under this paradigm, we will study three categories of online problems that have recently been defined or have seen recent major progress: Bigtable compaction policies, truthful mechanisms for combinatorial auctions, and scheduling problems.
- Spyros Angelopoulos, Sorbonne Université, chargé de recherche CNRS
- Vincent Cohen-Addad, Sorbonne Université, chargé de recherche CNRS
- Christoph Dürr, Sorbonne Université, directeur de recherche CNRS
- Chien-Chung Huang, Ecole Normale supérieure, chargé de recherche CNRS
- Claire Mathieu, Ecole Normale supérieure, directrice de recherche CNRS
- Abhinav Srivastav, Ecole Normale Superieure et Université Paris-Dauphine, postdoc
- Nguyễn Kim Thắng, Université Evry Val d’Essonne, maître de conférence
- Neal Young, University of California, Riverside, USA, professor
The project spans from september 2017 to august 2019.
We started with a kickoff meeting on september 22nd, and plan to end with a 3-day meeting in spring 2019. In between we try to meet every Friday afternoon.