CMU-CS-07-102Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-07-102
Sham Kakade*, Adam Tauman Kalai**, Katrina Ligett January 2007
Keywords: Approximation algorithms, regret minimization, online
linear optimzation
In an online linear optimization problem, on each period c(s,
where _{t},w_{t})c is a fixed cost function that is linear in the weight
vector. In the full-information setting, the vector
w is then revealed to the algorithm, and in
the _{t}bandit setting, only the cost experienced,
c(s, is revealed. The goal of the
online algorithm is to perform nearly as well as the best fixed
_{t},w_{t})s ∈S in hindsight. Many repeated decision-making problems
with weights fit naturally into this framework, such as online
shortest-path, online TSP, online clustering,
and online weighted set cover.
Previously, it was shown how to convert any efficient
We show how to convert any efficient offline
Our algorithm can also be viewed as a method for playing a large
repeated games, where one can only compute
19 pages
*Toyota Technological Institute at Chicago
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |