Thumbnail
Access Restriction
Open

Author Kalai, Adam ♦ Vempala, Santosh
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Upcoming Period ♦ Natural Online Version ♦ Optimal Static Solution ♦ Optimization Problem ♦ Online Optimization ♦ Linear Optimization ♦ Geometric Consideration ♦ Geometric Algorithm ♦ Objective Direction ♦ Present Algorithm
Description In this paper, we consider a natural online version of linear optimization: the problem has to be solved repeatedly over a sequence of periods, where the objective direction for the upcoming period is unknown. This models online versions of optimization problems, such as max-cut, variants of clustering, and also the classic online binary search tree problem. We present algorithms for this problem that are (1 + epsilon)-competitive with the optimal static solution chosen in hindsight. Our algorithms and proofs are motivated by geometric considerations.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2002-01-01
Journal Journal of Computer and System Sciences