Learning from a Sample in Online Algorithms
Main Conference Track
Authors: C.J. Argue, Alan Frieze, Anupam Gupta, Christopher Seiler

We consider three central problems in optimization: the restricted  assignment load-balancing problem, the Steiner tree network design  problem, and facility location clustering. We consider the online  setting, where the input arrives over time, and irrevocable decisions  must be made without knowledge of the future.  For all these problems, any online algorithm must incur a cost that is  approximately $\log |I|$ times the optimal cost in the worst-case,  where $|I|$ is the length of the input. But can we go beyond the  worst-case?  In this work we give algorithms that perform substantially  better when a $p$-fraction of the input is given as a sample: the  algorithm use this sample to \emph{learn} a good strategy to use  for the rest of the input.