Abstract | ||
---|---|---|
We attend to the classic setting where an observer needs to inform a tracker about an arbitrary time varying function f: ℕ0 →ℤ. This is an optimization problem, where both wrong values at the tracker and sending updates entail a certain cost. We consider an online variant of this problem, i.e., at time t, the observer only knows f(t′) for all t′≤t. In this paper, we generalize existing cost models (with an emphasis on concave and convex penalties) and present two online algorithms. Our analysis shows that these algorithms perform well in a large class of models, and are even optimal in some settings. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-13731-0_34 | SWAT |
Keywords | Field | DocType |
generalized penalty,large class,online algorithm,online variant,existing cost model,classic setting,optimization problem,certain cost,arbitrary time,convex penalty,varying function | Online algorithm,Mathematical optimization,Computer science,Regular polygon,Observer (quantum physics),Optimization problem,Penalty method,Competitive analysis | Conference |
Volume | ISSN | ISBN |
6139 | 0302-9743 | 3-642-13730-X |
Citations | PageRank | References |
6 | 0.54 | 15 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marcin Bienkowski | 1 | 254 | 27.18 |
Stefan Schmid | 2 | 769 | 79.85 |