Timezone: »

 
Spotlight
Learning from a Sample in Online Algorithms
C.J. Argue · Alan Frieze · Anupam Gupta · Christopher Seiler

Thu Dec 08 05:00 PM -- 07:00 PM (PST) @
in Lightning Talks 6B-2 »
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.
Keywords: Clustering · Optimization · online algorithms · Sample Complexity · Learning Augmented Algorithms · Facility Location · Steiner tree · Load Balancing

Author Information

C.J. Argue
Alan Frieze (Carnegie-Mellon University)
Anupam Gupta (Carnegie Mellon University)
Christopher Seiler (CMU, Carnegie Mellon University)

More from the Same Authors