Competitive On-line Routing (COL)
Developed by Plotkin et al.
ne = calls carried on edge e, ce = capacity of edge e
Does not assume traffic information
Motivated by competitive analysis
- Variant of COL is O( log n ) competitive ( n = #edges)
Off-line alg accepts < O( log n) (# calls accepted by COL)