Online Algorithms
Motivation:
till now, our algorithms start with input, work with it
(exception: data structures—come back later)
now, suppose input arrives a little at a time, need instant response
eg stock market, paging
question: what is a “good” algorithm.
depends on what we measure.
if knew whole input \(\sigma\) in advance, easy to optimize \(C_{MIN}(\sigma)\)
but online, early decision without complete info can mess you up
ski rental problem: rent 1, buy \(T\). don’t know how often we are going to ski.
notice that on some inputs, can’t do well! (stock market that only goes down, thrashing in paging)
problem isn’t to decide fast, rather what to decide.
Definition: competitive ratio
compare to full knowledge optimum
\(k\)-competitive if for all sequences etc. \(C_A(\sigma) \le kC_{MIN}(\sigma)\)
sometimes, to ignore edge effects, \(C_A(\sigma) \le kC_{MIN}(\sigma)+ O(1)\).
idea: “regret ratio”
analyze ski rental
Only choice is after how many days to buy.
If I rent \(d\) days and then buy (total cost of \(d+T\)) what is worst competitive ratio for me?
Before I buy skis, ratio is 1 if adversary knows should be renting, and keeps getting worse if adversary has bought. Either way, ratio not improving.
Once I have bought, my cost doesn’t increase and adversary’s doesn’t decrease, so ratio doesn’t worsen
combine: worst ratio is at moment I have bought skis (adversary will stop there).
I pay \(d+T\), adversary pays \(\min(d+1,T)\)
when \(d+1 \le T\) this is \((d+T)/T\) which decreases with \(T\), so best at \(d+1=T\).
Ratio \((d+T)/\min(d+1,T)\) minimized at \(d+1=T\).
ratio is \(2-1/T<2\).
we think of competitve analysis as a (zero sum) game between algorithm and adversary. Want to find the best strategy for algorithm.
supposed to be competitive against all sequences. So, can imagine that adversary is adapting to algorithm’s choices (to get worst sequence)
Finance
Known or unknown duration. But assume know which offer is last.
Need fluctuation ratio \(\phi\) between largest \(M\) and smallest \(m\) price.
even if know \(\phi\) but don’t know \(m\), can just run alg after seeing first price
Selling peanuts:
Break into \(\log \phi\) groups of equal amounts
Sell group \(i\) for value \(m \cdot 2^i\)
One group sold for at least half of max price
So achieve \(\log \phi\) competitive
Selling (one) car: Best deterministic algorithm: agree to first price exceeding \(\sqrt{Mm}\)
\(\sqrt{\phi}\) competitive
note have to know when last offer
Can achieve \(\log \phi\) randomized
Consider powers of 2 between \(m\) and \(M\)
Choose one at random
sell all at first bid exceeding
with prob \(1/\log \phi\), pick the power of 2 that is within factor 2 of highest offered price.
Graham’s Rule
Define \(P||\max C_j\) to minimize load.
NP-complete to solve exactly!
Always assign to least loaded machine:
any alg has 2 lower bounds: average load and maximum job size.
Suppose \(M_1\) has max load \(L\), let \(p_j\) be biggest job.
claim every machine has \(L-p_j\) (else wouldn’t have assigned last job to \(M_1\)
thus total load at least \(\sum p_i = m(L-p_j)+p_j\)
thus OPT \(\ge L-p_j+p_j/m\)
but OPT\(\ge p_j\), so \((2-1/m)OPT \ge L\)
More recent algs do somewhat better:
keep some machines small
algorithms not too bad, proofs awful!
Bartal et al ’95: 2-1/70=1.986
Karger et al ’96: 1.945
Albers ’97: 1.923
Paging problem
define: on miss, must evict
LRU, FIFO, LIFO, Flush when full, Least Freq Use
LIFO, LFU not competitive
LRU, FIFO \(k\)-competitive.
will see this is best possible (det)
Easy argument: \(k+1\) competitive
break into maximal phases of \(k+1\) faults
if phase has only \(k\) distinct pages, at most \(k\) faults
thus, \(k+1\) distinct requests
OPT faults on one
With work, we can improve to \(k\) (worth it for tightness):
break into phases: maximal groups containing \(k\) faults
(so group starts with a fault)
let \(q\) be last page before current phase
so \(q\) initially in memory
case 1: LRU faults on \(q\)
then must see \(k\) other pages to evict \(q\)
so see \(k+1\) requests including \(q\) request
so OPT must fault
case 2: LRU faults on a different page, twice
again, to evict that page must see \(k\) other pages between faults
so \(k+1\) distinct pages
so OPT faults
case 3: no fault on \(q\) or twice on any page
\(q\) is in cache at start and stays there
\(k\) other requests must occur to cause \(k\) faults
so \(k+1\) request in total
Generalize: LRU is \(k/(k-h+1)\) competitive against \(h\)-page adversary
Observations:
proved without knowing optimum
instead, derived lower bound on cost of any algorithm
same argument applies to FIFO.
Lower bound: no online algorithm beats \(k\)-competitive.
set of \(k+1\) pages
always ask for the one \(A\) doesn’t have
faults every time.
so, just need to show can get away with 1 fault every \(k\) steps
have \(k\) pages, in memory. When fault, look ahead, one of \(k+1\) isn’t used in next \(k\), so evict it.
one fault every \(k\) steps
so \(A\) is only \(k\)-competitive.
Observations:
Lower Bound can be proven without knowing OPT, often is.
competitive analysis doesn’t distinguish LRU and FIFO, even though know different in practice.
still trying to refine competitive analysis to measure better: SODA paper: “LRU is better than FIFO”
applies even if just have \(k+1\) pages!
Optimal offline algorithm: Longest Forward Distance
evict page that will be asked for farthest in future.
suppose MIN is better than LFD. Will make NEW, as good, agrees more with LFD.
Let \(\sigma_i\) be first divergence of MIN and LFD (at page fault)
LFD discards \(q\), MIN discards \(p\) (so \(p\) will be accessed before \(q\) after time \(i\))
Let \(t\) be time MIN discards \(q\)
revise schedule so MIN and LFD agree up to \(t\), yielding NEW
NEW discards \(q\) at \(i\), like LFD
so MIN and NEW share \(k-1\) pages. will preserve till merge
in fact, \(q\) is unique page that MIN has that NEW doesn’t
case 1: \(\sigma_i,\ldots,\sigma_t,\ldots,p,\ldots,q\)
until reach \(q\)
let \(e\) be unique page NEW has that MIN doesn’t (init \(e=p\))
when get \(\sigma_l\ne e\), evict same page from both
note \(\sigma_l \ne q\), so MIN does fault when NEW does
both fault, and preserves invariant
when \(\sigma_l=e\), only MIN faults
when get to \(q\), both fault, but NEW evicts \(e\) and converges to MIN.
clearly, NEW no worse than MIN
case 2: \(t\) after \(q\)
follow same approach as above till hit \(q\)
since MIN didn’t discard \(q\) yet, it doesn’t fault at \(q\), but
since \(p\) requested before \(q\), had \(\sigma_l=e\) at least once, so MIN did worse than NEW. (MIN doesn’t have \(p\) till faults)
so, fault for NEW already paid for
still same.
prove that can get to LFD without getting worse.
so LFD is optimal.
Move to front
Studying heuristics for reorganizing a list after you access it
a natural heuristic: move accessed item towards front
maybe all the way to front?
is it a good heuristic?
compare to omniscient algorithms that can move accessed item any amount towards front (or not at all)
so e.g. won’t move item to front if not accessed again soon
Potential function: number of inversions.
amortized cost: real plus potential
summing telescopes potential and leaves real cost
suppose search for item \(x_j\) at \(j\) in opt, at \(k\) in MTF
suppose \(v\) items precede in MTF but not OPT
then \(k-v-1\) precede in BOTH
so \(k-v-1 \le j-1\) so \(k-v \le j\)
MTF creates \(k-v-1\) new inversions and kills \(v\) old ones,
so amortized cost is \(k+(k-v-1)-v \le 2(k-v)\le 2j\)
now do opt’s move.
moving \(x_j\) towards front only decreases inversions (since \(x_j\) already at front in MTF)
so cannot increase potential
so doesn’t increase amortized cost of access
Strengthen
we can allow adversary to make arbitrary transposes
if we charge the adversary 1 for each transpose
since then any increase in potential (and thus our amortized cost) is upper bounded by the adversary’s cost
so we remain 2-competitive vs. algorithm that can move accessed item anywhere and then do any transposes it likes
Lower bound:
suppose \(n\) items in list
nasty algorithm: always request last in list
generates a sequence of length \(m\)
total cost \(mn\)
consider alg that picks random order and doesn’t change
expected access time for each item is \((n-1)/2\)
expected total cost \(m(n-1)/2\)
some algorithm achieves that cost
offline alg can use that one
ratio \(2n/(n-1) \rightarrow 2\)
Note: our competitive bound assumes opt is paying 1 for transposes
if opt can rearrange anything it sees, can’t beat \(\Omega(n/\log n)\) competitive
“Order by Next Request” heuristic—rearrange everything you pass
Munro 2000
achieves cost equal to entropy
so consider a uniform random sequence
entropy is \(O(\log n)\)
an online algorithm will pay \(n/2\) in expectation every time.
so \(\Omega(n/\log n)\) competitive
2011 End lecture 20
Randomized Online Algorithms
An online algorithm is a two-player zero sum game between algorithm and adversary. Well known that optimal strategies require randomization.
A randomized online algorithm is a probability distribution over deterministic online algorithms.
idea: if adversary doesn’t know what you are doing, can’t mess you up.
idea: can’t see adversary’s “traps”, but have certain probability of wiggling out of them.
in practice, don’t randomly pick 1 det algorithm at start. Instead, make random choices on the way. But retrospectively, gives 1 deterministic algorithm.
Algorithm is \(k\)-competitive if for any \(\sigma\), \(E[C_A(\sigma)] \le k\cdot OPT+O(1)\).
Adversaries:
oblivous: knows probability distribution but not coin tosses. Might as well pick input in advance.
fully adaptive: knows all coin tosses. So algorithm is deterministic for it.
adaptive: knows coin tosses up to present—picks sequence based on what did.
clearly adaptive stronger than oblivious.
oblivious adversary plausible in many cases (eg paging)
problematic if online behavior affects nature (eg, paging an alg that changes behavior if it sees itself thrashing)
our lower bound applies to adaptive
but in other cases, can do better against adaptive
we’ll show much better vs. oblivous
Randomized Paging
Idea: evict random page?
\(k\)-competitive against adaptive adversary
but uses no memory
trading space for randomness
Marking algorithm:
initially, all pages marked (technicality)
on fault, if all marked, unmark all
evict random unmarked page
mark new page.
Fiat proved: Marking is \(O(\log k)\) competitive for \(k\) pages.
Phases:
first starts on first fault
ends when get \(k+1^{st}\) distinct page request.
so a phase has \(k\) distinct pages
cost of \(M\) is cost of phases
note: defined by input, independent of coin tosses by \(M\)
but, marking tracks:
by induction, unmark iff at end of phase
by induction, all pages requested in phase stay marked till end of phase
so, pay for page (if at all) only on first request in phase.
by induction, at end of phase memory contains the \(k\) pages requested during the phase.
Analysis:
ignore all but first request to a page (doesn’t affect \(M\), helps offline)
compare phase-by-phase cost
phase \(i\) starts with \(S_i\) (ends with \(S_{i+1}\))
request clean if not in \(S_i\). \(M\) must fault, but show offline pays too
request stale if in \(S_i\). \(M\) faults if evicted during phase. Show unlikely.
Online cost:
Expected cost of stale request:
suppose had \(s\) stale and \(c\) clean requests so far.
at this point, we have \(s+c\) pages marked in memory \(\Rightarrow\) all the original locations of the \(s\) stale requests are taken (possibly some by clean requests that bumped out stale pages) and additional \(c\) out of these marked pages (some of them can be stale) needed to bump out the remaining \(k-s\) pages.
what prob current request was evicted? By symmetry, \(c/(k-s)\)
this is expected cost of stale request.
Cost of phase.
Suppose has \(c_i\) clean requests, \(k-c_i\) stale.
Pay \(c_i\) for clean.
for stale requests, pay at most \[c_i(\frac1k+\frac1{k-1}+\cdots+\frac{1}{c_i+1}) =c_i(H_k-H_{c_i})\]
so total at most \(c_i\log k\)
Offline cost:
potential function \(\Phi_i=\) difference between \(M\) and \(O\) (offline) at start of phase \(i\).
got \(c_i\) clean requests, not in \(M\)’s memory. So at least \(c_i-\Phi_i\) not in \(O\)’s memory.
at end of round, \(M\) has all \(k\) most recent requests. So \(O\) is missing \(\Phi_{i+1}\) of \(k\) this round’s requests. Must have evicted (thus paid for) them.
so, \(C_i(O) \ge \max(c_i-\Phi_i,\Phi_{i+1}) \ge \frac12(c_i+\Phi_i-\Phi_{i+1})\).
sum over all phases; telescopes. Deduce \(C_i \ge \frac12 \sum c_i\).
Summary: If online pays \(x\log k\), offline pays \(x/2\). So, \((\log k)\)-competitive.
Lower Bounds via Yao’s Minimax Principle
Online algorithms is a two player game:
online wants to optimize ratio, adversary want it to be bad
online chooses random alg, adversary chooses random input
leads to payoff matrix—expected value of game
number in matrix is ratio for alg on that input
in general, optimal strategy of both sides is randomized
Von Neumann proved equality of minimax and maximins
notice: player who picks strategy second can use deterministic choice
note when one player’s strategy known, other player can play deterministically to meet optimum.
above, assumed adversary knew online’s strategy, so he played deterministically
for lower bound, we let adversary have randomized strategy, look for best deterministic counter!
If give random input for which no deterministic alg does well, we get a lower bound.
Formalize:
say online \(A\) is \(k\)-competitive against an input distribution \(p_\sigma\) if \(E_\sigma(C_A(\sigma)) \le cE_\sigma(C_{OPT}(\sigma))\) (note: OPT gets to see sequence before going)
Theorem: if for some distribution no deterministic alg is \(k\)-competitive, than no randomized algorithm is \(k\)-competitive.
to prove, suppose have \(k\)-competitive randomized alg, show det \(k\)-competitive against any \(\sigma\).
consider payoff \(E_{A} [C_A(\sigma) - kC_{OPT}(\sigma)]\)
by assumption, some dist on \(A\) achieves non-positive payoff.
remains true even if choose best possible randomized strategy on \(\sigma\)
once do so, have deterministic counter \(A\)
so for any \(p_\sigma\) on \(\sigma\), some \(A\) such \(E_{\sigma}[C_A(\sigma)-kC_{OPT}(\sigma)] \le 0\)
in other words, \(A\) is \(k\)-competitive against \(p_\sigma\).
For paging:
set of \(k+1\) pages
uniform random sequence of requests
any deterministic (or randomized!) algorithm has an expected \(1/{k}\) fault per request. So cost \(n/k\) if seq length \(n\)
what is offline cost? on fault, look ahead to page that is farthest in future.
phase ends when all \(k+1\) pages requested
offline faults once per phase
how long is a phase? coupon collection. \(\Omega(k\log k)\).
intuitively, number of faults is \(n/k\log k\)
formally, use “renewal theory” that works because phase lengths are i.i.d.
deduce expected faults \(n/k\log k\), while online is \(n/k\)
\(\log k\) gap, so online not \(\log k\)-competitive.
This analysis applies to an oblivious adversary. What about other models?
a fully adaptive adversary knows all your coin flips, so for them you are deterministic.
it’s known that if you can be \(c\)-competitive versus a partially adaptive adversary and \(d<c\)-competitive against an oblivious one then you can be \(dc\)-competitive deterministically.
so, since we know \(d=O(\log k)\) for paging, we conclude you can’t beat \(k/\log k\) against a partially adaptive adversary. Note sure if that has been achieved.
\(k\)-server
Manasse et al. 1988.
Definition:
metric space with \(k\) servers on points
request is a point in space
must move a server, cost is distance.
eg taxi company
paging is special case: all distances \(1\), servers on “memory pages”
also multi-head disks
compute offline by dynamic program or reduction to min cost flow
Greedy doesn’t work:
2 servers, 1 far away, other flips between 2 points.
need an algorithm that moves a far away server sometimes in case a certain region is popular
Fancy algorithmics:
HARMONIC: randomized, move with probability inversely proportional to distance from goal: \(O(k^k)\) [Fiat, Rabani, Ravid]
WORK FUNCTION: track what offline algorithms would have done (computationally very expensive) and then do your best to move into a similar configuration.
define \(W_i(X)\) to be opt cost of serving first \(i\) requests and ending with servers in state \(X\)
choose configuration \(X_i\) to optimize \(\min_X W_i(X)+d(X_{i-1},X)\)
you do this when you are already in state \(X_{i-1}\) that you picked in the previous request
in 2001, work-function was proven 2k-competitive using a black magic potential function
conjectured \(k\)-competitive.
exponential time to compute a move!
questions remain on finding an algorithm that does little work per input.
On a Line
A truly “On Line” algorithm.
greedy algorithm bad if requests alternate \(a\) near \(b\) but server on distant \(c\).
Intuition
What is optimum action right now if you know the future?
Move one of nearest items
Since moving anything else will eventually cross a nearest
so might as well move nearest instead, then replace it later
Problem: which of two nearest to move?
double coverage algorithm (DC):
If request outside convex hull, move nearest point to it.
else, move nearest point on each side towards it equal distance till one hits.
\(k\)-competitive.
let \(M\) be min-cost matching of opt points to DC points
let \(d\) is distance between servers in DC
\(\Phi=kM+\sum_{i < j}d(s_i,s_j)\)
analyze change when (first) adversary moves, (then) DC moves
show:
if adversary moves \(d\), increases \(\Phi\) by \(\le kd\)
if DC moves moves \(d\), decreases \(\Phi\) by \(d\)
deduce: DC is \(k\)-competitive
assume start in same configuration at starting node
then \(\Phi=0\)
\(\Phi\) always positive
if DC moves more than \(k\) times OPT, get \(\delta\Phi\) negative
but can’t have negative \(\Phi\)
if start in different configuration
adds a constant (dependent on metric space) to \(\Phi\)
so asymptotically \(k\)-competitive.
Analysis:
adv moves \(d\) just increases \(M\) by \(d\), so \(\Delta \Phi \le kd\)
Consider DC move to outside hull,
adversary already has a point at destination;
WLOG moving point matched to it (else matches something else; uncross).
so \(\Delta M=-d\)
\(\Delta \Sigma = (k-1)d\).
claim follows: \(\Delta \phi = -kd+(k-1)d = -d\)
consider DC move to inside hull
Consider \(M\)
one of moving points is matched to request.
So that move decreases \(M\).
Other move may increase \(M\) at most by same amount,
so no change to \(M\).
Now consider \(\Sigma\).
Moves of two points cancel out with respect to other points
but they get \(2d\) units closer.
Generalizes to trees.
Which yields randomized \(O(\log^3 n \log^2 k)\) for general \(k\)-server via tree embeddings.
Can we do better? No, because paging is special case.