AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We consider the problem of reading articles appearing in a dynamic stream while maximizing the information gain within a restricted amount of time. Upon arrival, an article reveals its length and a hint about its content. In each time step, the reader has to decide whether to read the next portion of the current article or to skip the remaining part irrevocably. In this work, we first show unlimited lower bounds for certain parameter settings. With restrictions derived from these bounds, we show that any \alpha-competitive algorithm for the Online Knapsack Problem in the random order model can be used as a black box to obtain an (e + \alpha)C-competitive algorithm for Reading Articles Online, where C measures the accuracy of the hints with respect to the average information rate of any article. With the current best algorithm for Online Knapsack, we obtain an upper bound of 3.45eC on the competitive ratio of Reading Articles Online. Moreover, we study a natural algorithm that uses a single threshold value for its decisions. We show that this technique is O(C)-competitive and, therefore, constant-competitive whenever the accuracy C is a constant.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak

--email hidden

passcode not visible

logged in users only

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.