On-line complexity of monotone set systems
Haim Y. Kaplan, Márió Szegedy · 1999
On-line analysis models a player A (randomized or deterministic) who makes immediate responses to incoming elements of an input sequence s = a1 : : : ar . In this paper a1 ; : : : ; ar are interpreted as elements offered without repetition to the player from a fixed universe and the player's response to each a i is a single bit interpreted as pick/not-to-pick. Before seeing the stream s, the player is given a monotone system M of sets indicating all sets of elements that she is allowed to hold at any time during the game and the player's objective is to pick as many elements as possible under these constraints. We assign the performance measure e(M) = maxA mins E(jA(s)j)=OPT (s) to every monotone set system M, where E() is the expectation over the player's random choices and OPT (s) = maxM2M jM " sj. Note that for every M, e(M) 2 [0; 1], and it is easy to show that a system has performance one iff it is a matroid. This model generalizes the apparently unrelated models in [2] and [3]. ...