Alexander's Notes

Competitive Analysis

7 min read

Summary

Introduces competitive analysis for online algorithms that receive inputs one at a time. Defines 𝛼-competitiveness against the optimal offline algorithm. Analyzes the Move-to-Front heuristic for self-organizing lists, proving it is 4-competitive via the [[Amortized Analysis#|potential method]] by tracking inversions between the MTF and OPT lists.

Competitive algorithms are concerned with cases where we only get inputs one at a time. Offline algorithms have access to the whole data structure in question, which makes it inherently more efficient and capable. We will be discussing ways to optimize cases where we don’t have access to all information at once.

To define efficiency, we will compare our online algorithms to our best possible offline algorithm and minimize how much worse it is for all prefixes of input.

Definition

A deterministic online algorithm 𝐴 is 𝛼-competitive if for all sequences 𝑅, the cost𝐴(𝑅)≀𝛼costOPT(𝑅)+𝑐.

Self-Organizing Lists

Given 𝑛 distinct elements, we need to control:

  • Access(x) - Find and return π‘₯ The cost of access is the rank of x, which tautologically is the index of π‘₯ in 𝐿.

Example

Index12345
𝐿ACBED

Access(B) has cost 3, since 𝐡 is at index 3.

Now, if we want to access 𝐷 a lot in our example, keeping it at the end would be quite inefficient. The key is to find the best way to arrange the list to be helpful to us.

Let us say that after every access, we can rearrange the list via transpositions between adjacent elements, wherein they are swapped. We will charge a cost of 1 for each transposition. So after any given access(x) we perform the access and then do some transpositions. We will call each arrangement of the list as

𝐿0→𝐿1→𝐿2→…

We will thus rigorously define our cost as

Cost𝐴(𝑅)=βˆ‘π‘˜π‘–=1[Rank𝐿𝑖1(π‘₯𝑖)+𝑑𝑖]

The worst-case runtime is Ξ©(𝑛⋅|𝑅|). This might seem bad, but if the best offline algorithm is already bad, it’s pretty competitive.

Our adversary might want to exploit this data structure by querying as follows (reminder that 𝑅 is the order of their queries):

𝐿=[1,…,𝑛]𝑅={𝑛,π‘›βˆ’1,…,1}

If we do no transpositions, this would take Θ(𝑛2). We cannot do better than this, unfortunately, so our algorithm is good compared to the optimal offline one.

Now let us say we access the same element over and over again.

𝐿=[1,…,𝑛]𝑅={𝑛,𝑛,…,𝑛}

The optimal approach would be to transpose 𝑛 to the front. The total cost would be 𝑛 for the first access plus π‘›βˆ’1 transpositions to move 𝑛 to the front plus π‘›βˆ’1 queries of cost 1. Hence, the optimal solution is 𝑂(𝑛). The difficulty is for our online algorithm to β€œsee” this, as it won’t know that each query is 𝑛.

Move-to-Front (MTF)

After Access(x_i), move x_i to the front via transpositions.

CostMTF(𝑅)=βˆ‘π‘˜π‘–=1[2βˆ—RankπΏπ‘–βˆ’1(π‘₯𝑖)βˆ’1]

where πΏπ‘–βˆ’1 is the list before the transposition.

Theorem

MTF is 4-competitive.

We will spend the rest of the lecture proving this statement. The key idea is to track how far MTF’s list diverges from OPT’s list at each step, and show the distance stays bounded.

We need some notation.

π‘Ÿπ‘–=RankπΏπ‘–βˆ’1(π‘₯𝑖)π‘Ÿβˆ—π‘–=RankπΏβˆ—π‘–βˆ’1(π‘₯𝑖)𝑐𝑖=2π‘Ÿπ‘–βˆ’1π‘βˆ—π‘–=π‘Ÿβˆ—π‘–+𝑑𝑖

where 𝑑𝑖 is the number of transpositions done at step 𝑖.

Hence, CostMTF(𝑅)=βˆ‘π‘π‘– and CostOPT(𝑅)=βˆ‘π‘βˆ—π‘–. We will solve this with the potential method with a function Ξ¦ such that Φ𝑖β‰₯Ξ¦0 for all 𝑖. Recall that ΔΦ𝑖=Ξ¦π‘–βˆ’Ξ¦π‘–βˆ’1 and ̂𝑐𝑖=𝑐𝑖+ΔΦ𝑖.

βˆ‘π‘˜π‘–=1̂𝑐𝑖=βˆ‘π‘˜π‘–+1𝑐𝑖+βˆ‘π‘˜π‘–=1ΔΦ𝑖=βˆ‘π‘˜π‘–+1𝑐𝑖+Ξ¦π‘˜βˆ’Ξ¦0β‰₯βˆ‘π‘˜π‘–+1𝑐𝑖

We apply Ξ¦ to (𝐿,πΏβˆ—). An inversion between 𝐿𝑖 and πΏβˆ—π‘– to be a pair (π‘₯,𝑦) where π‘₯<𝐿𝑖𝑦 and π‘₯>πΏβˆ—π‘–π‘¦.

In other words, this means B is before D in the MTF solution, but after D in the OPT solution. We now define our potential function as

Φ𝑖=Ξ¦(𝐿𝑖,πΏβˆ—π‘–)=2Γ—# inversions between𝐿𝑖andπΏβˆ—π‘–

Intuitively, tracking inversions gives us a pseudo-distance between the two lists. We can find how many transpositions are needed to go between the two lists. Ξ¦0=0 because the two lists are the same, and all Φ𝑖β‰₯Ξ¦0, so this is a valid potential function.

  • Access(x_i) - ΔΦ=0.
  • Transposition between (x,y) in 𝐿𝑖 - Assuming π‘₯ was before 𝑦 before in both lists, the pair becomes an inversion. Hence, ΔΦ𝑖=2. If there was an inversion before, then ΔΦ𝑖=βˆ’2.

When MTF moves π‘₯𝑖 to the front, it passes over every element 𝑦 that was before π‘₯𝑖 in πΏπ‘–βˆ’1. We classify each element 𝑦≠π‘₯𝑖 by its position relative to π‘₯𝑖 in both lists:

  • 𝐴𝑖 - before π‘₯𝑖 in πΏπ‘–βˆ’1 and before π‘₯𝑖 in πΏβˆ—π‘–βˆ’1. The pair (𝑦,π‘₯𝑖) had the same order in both lists. MTF moves π‘₯𝑖 ahead of 𝑦, creating an inversion. ΔΦ=+2 per element.
  • 𝐡𝑖 - before π‘₯𝑖 in πΏπ‘–βˆ’1 but after π‘₯𝑖 in πΏβˆ—π‘–βˆ’1. The pair was already an inversion. MTF moves π‘₯𝑖 ahead of 𝑦, removing it. ΔΦ=βˆ’2 per element.
  • 𝐢𝑖 - after π‘₯𝑖 in πΏπ‘–βˆ’1, before π‘₯𝑖 in πΏβˆ—π‘–βˆ’1. MTF doesn’t change the relative order of 𝑦 and π‘₯𝑖. Unaffected.
  • 𝐷𝑖 - after π‘₯𝑖 in πΏπ‘–βˆ’1 and after π‘₯𝑖 in πΏβˆ—π‘–βˆ’1. Also unaffected.

Notice that π‘Ÿπ‘–=|𝐴𝑖|+|𝐡𝑖|+1 and π‘Ÿβˆ—π‘–=|𝐴𝑖|+|𝐢𝑖|+1. Before we do anything, 𝐡𝑖 and 𝐢𝑖 contain our inversions.

ΔΦ𝑖,MTF=2(|𝐴𝑖|βˆ’|𝐡𝑖|)ΔΦ𝑖,OPT≀2𝑑𝑖ΔΦ𝑖≀2(|𝐴𝑖|βˆ’|𝐡𝑖|+𝑑𝑖)

Now we consider our amortized cost.

\
&<= 2r_i - 1 + 2(|A_i| - |B_i| + t_i) & ("def. of" c_i "and" Delta Phi_i) \
\
&= 2r_i - 1 + 2(|A_i| - (r_i - |A_i| - 1) + t_i) & (|B_i| = r_i - |A_i| - 1) \
\
&= 4|A_i| + 2t_i + 1 & ("simplify") \
\
&<= 4(|A_i| + |C_i|) + 4t_i + 1 & (|C_i| >= 0, t_i >= 0) \
\
&= 4(r_i^* - 1) + 4t_i + 1 & (r_i^* = |A_i| + |C_i| + 1) \
\
&<= 4(r_i^* + t_i) = 4c_i^* & square$$
We proved $c_i < 4c_i^*$.

## More on Competitive Analysis
In an online setting, you need to design the algorithm given that you don't know the full sequence of events upfront. This is much trickier than in offline algorithms, where you're given all the information immediately. **Competitive Analysis** involves a sequence of requests/inputs, and you want the algorithm to be as good compared to the online one as possible. 


> [!example] Example - Job Scheduling
> 
> We have a sequence of jobs arriving one at a time: $J_1, J_2, dots$. As each one comes in, we must assign it to a machine. The goal is to minimize the **makespan** β€” the longest total time any machine works.
>
> ![[attachments/job-scheduling-online.svg|500]]
> 
> One idea is to greedily select the current machine with the earliest finish time. We want to show $C_"greedy" <= alpha dot C_"OPT"(R) + "constant"$

Graph View

Recent Notes

See 55 more β†’