Title: Theory / Unimportant / CS / Fundamental / Complexity / Wigderson / 16 On-line algorithms
Tags: fromMath mathToSee

Name: A \(c\)-competitive online algorithm for \(O\)
Definition: An algorithm \(A\) such that \(C_A(e)\le c\cdot Opt(e)+M\) for some fixed constant \(M\) and every sequence \(e\)
Page: 204
Chapter: 16
Variables: \(O=(E,D,C)\) an on-line problem,
\(c\ge0\)

Name: A competitive online algorithm for \(O\)
Definition: A \(c\)-competitive algorithm for \(O\), for some \(c\ge0\)
Page: 204
Chapter: 16
Variables: \(O=(E,D,C)\) an on-line problem,

Name: An on-line problem
Definition: A set \(E\) of events
Page: 205
Chapter: 16
Section: 1
Definition2: a set \(D\) of decisions
Conjdef: The tuple
Definition3: a family of cost functions \(C=\{C_t:E^t\times D^t\to\mathbb R\}\) for every integer \(t\)

Name: The input of \(O\)
Typ: An element of \(E^*\)
Page: 205
Section: 1
Chapter: 16
Variables: \(O=(E,D,C)\) an on-line problem
Denoted by: \(e\)

Name: The event at time \(t\)
Page: 205
Chapter: 16
Section: 1
Variables: \(O=(E,D,C)\) an on-line problem,
\(e\) an input
Notation: \(e_t\)

Name: An on-line algorithm
Definition: A sequence of functions \(A_t:E^t\to D\) specifying the next decision given the input so far.
Page: 205
Chapter: 16
Section: 1
Variables: \(O=(E,D,C)\) an on-line problem,
Denoted by: \(A\)

Definition: \(A_1(e^1),\dots, A_T(e^T)\)
Page: 205
Chapter: 16
Section: 1
Variables: \(O=(E,D,C)\) an on-line problem,
\(A\) an on-line algorithm
\(e=e_1,\dots,e_T\) an input
Notation: \(A(e)\)

Name: The cost of \(A\) incurring in step \(t\)
Definition: \(C_t(e,A(e^t))\)
Page: 205
Chapter: 16
Section: 1
Variables: \(O=(E,D,C)\) an on-line problem,
\(A\) an on-line algorithm
\(e=e_1,\dots,e_T\) an input

Name: The total cost incurred by \(A\)
Definition: \(\sum_{t=1}^T C_t(e^t,A(e^t))\)
Page: 205
Chapter: 16
Section: 1
Variables: \(O=(E,D,C)\) an on-line problem,
\(A\) an on-line algorithm
\(e=e_1,\dots,e_T\) an input
Notation: \(C_A(e)\)

Name: The off-line cost of \(e\)
Definition: The minimal over \(d\) of \(\sum_{t=1}^TC_t(e^t,d^t)\)
Page: 205
Chapter: 16
Section: 1
Variables: \(O=(E,D,C)\) an on-line problem,
\(e=e_1,\dots,e_T\) an input
Name2: The optimal cost of \(e\)
Intuition: The minimum cost incurred by the best sequence of decisions.
Abbreviation2: \(OPT(e)\)

Q: [...] is an example of [...]
A: Predicting the next entry (or paying a cost of 1); algorithm for which there is no competitive algorithm
Page: 205
Chapter: 16
Section: 1

Smaller0: \(\mathcal E\) is compact
Greater0: closed
Page: 228
Chapter: 4
Section: 3
Variables: \(\mathcal E\subseteq C^0([a,b],\mathbb R)\).
Index: 18
Kind: Theo
Smaller to greater: iff
Prefix Greater: \(\mathcal E\) is
Greater1: bounded
Greater2: equicontinuous