PGMO project

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.

Members

Project management

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.