Is the offline optimum a real implementable online policy?

Usually it is a hindsight benchmark that can use future information unavailable to the online algorithm.

Does a ratio of 2 mean twice as slow?

No. It concerns the specified objective, such as total cost, rather than necessarily execution time.

Can experiments prove a universal competitive ratio?

Finite tests alone generally cannot. A proof must cover the allowed sequences or a genuinely exhaustive finite model.

AI Glossary / Graphs and symbolic AI / Intermediate

Competitive ratio

Definition

A competitive ratio measures an online algorithm's performance against an optimal offline algorithm that knows the entire input sequence in advance. For a cost-minimization problem, a ratio c means the online algorithm's cost is at most c times the offline optimum under the stated definition. It evaluates decisions made without knowledge of future requests.

What it means

An online algorithm must act as information arrives. It may need to accept a request, allocate a resource, or decide whether to keep renting without knowing how long demand will continue.

The offline optimum provides a hindsight benchmark. It follows the same modeled feasibility rules but has advance knowledge of the complete input. The comparison asks how much the lack of future information can cost the online strategy.

A competitive ratio is normally a worst-case guarantee over the permitted input sequences, not the ratio observed on one test. For minimization, smaller ratios are better, and a ratio of 1 means matching the optimum under the comparison. Maximization problems use an appropriately reversed convention, which should be stated explicitly.

How it works

Specify the input sequences, legal actions, cost function, and information available when each decision is made. Let ALG(s) denote the online cost for sequence s and OPT(s) the minimum offline cost.

A strict c-competitive guarantee states ALG(s) is no greater than c times OPT(s) for every permitted sequence. Some definitions allow an additional constant term independent of the sequence. That distinction matters, especially for small instances or cases where the optimum is zero.

Proving a ratio requires an argument covering all relevant sequences. Testing many examples can reveal a counterexample to a proposed bound but does not by itself establish the universal guarantee.

Randomized algorithms add further choices. A result may bound expected cost over the algorithm's random choices, and the adversary's access to those choices affects the model. Such a guarantee should not be presented as a deterministic bound on every individual run.

Three practical examples

1. A caching researcher compares an online replacement policy with an offline policy that knows future page requests.

2. A resource-management study evaluates a rent-or-buy rule against the cheapest decision that could have been made with complete knowledge of demand duration.

3. An online scheduling analysis measures the cost of committing to assignments as jobs arrive, using an offline scheduling benchmark.

Think of it this way

Think of planning purchases while the shopping list arrives one item at a time, then comparing your spending with a planner who saw the whole list beforehand.

The analogy emphasizes unequal information. The comparison is meaningful only if both planners face the same modeled prices and legal options; hindsight does not grant the offline benchmark unrelated extra resources.

Worked example

Consider a rental problem. Renting costs 1 unit per day, while buying costs 5 units and covers every subsequent day. Demand lasts an unknown positive integer number d of days. Ignore additional costs.

Use this strategy: rent for the first four days if demand continues, then buy at the start of day five if needed. For d from 1 through 4, the strategy costs d. The offline optimum also costs d, so the ratio is 1.

For d at least 5, the strategy costs 4 + 5 = 9. The offline optimum buys immediately for 5, so the ratio is 9/5 = 1.8. These two cases cover every permitted duration, establishing a strict 1.8 competitive bound for this strategy in the stated model.

One duration alone would not establish the bound. The result also does not automatically transfer to a rental contract with changing prices or cancellation fees.

Illustrative case study

Fictional case: Crestline Computing evaluates a rule for moving a repeatedly used temporary resource to a longer-term allocation. The research team creates a simplified rent-or-buy model and derives a competitive guarantee for it.

Operations staff then identify costs absent from the model, including transition work and variable demand. The team keeps the theorem attached to its assumptions and measures the proposed rule on representative operational scenarios.

This fictional case illustrates a useful relationship between analysis and deployment evidence. A competitive ratio can explain worst-case behavior within a model, while practical adoption still depends on whether that model captures the relevant decisions and costs.

Common misconceptions and mistakes

A competitive ratio is not an average improvement over the current business process. Its benchmark is an explicitly defined offline optimum, and the guarantee usually concerns worst-case sequences.

It is not the same as computational running time. An algorithm can make high-quality online decisions while requiring substantial computation, or run quickly while having a poor ratio.

Do not report the largest ratio seen in a finite test as a proven competitive ratio. Label it as an observed result unless a covering argument exists.

Finally, do not compare ratios from different information models or objectives as if they measured the same task. Randomization, predictions, resource augmentation, and additive constants can change the meaning of a claim.

Business use

For business users, competitive analysis can clarify the downside of decisions made before future demand is known. It is particularly useful when assumptions about the request sequence are intentionally weak.

A useful report names the objective, offline benchmark, permitted inputs, information model, and whether the guarantee is strict, additive, or expected. Pair the theorem with actual workload evaluation. A strong worst-case guarantee and good typical performance are distinct properties, and either may matter for the decision being made.

Check your understanding

In the rental example, demand lasts eight days. What are the strategy's cost, the offline cost, and their ratio?

Answer: The strategy pays 9, the offline optimum pays 5, and the ratio is 1.8. The earlier case analysis establishes that this ratio also bounds all permitted positive integer durations.

Related terms

Online algorithm
offline optimum
competitive analysis
worst-case analysis
adversary model
randomized algorithm
ski-rental problem
approximation ratio

Learn next

Change the rental strategy's purchase day and analyze both short and long demand sequences. Identify the worst case rather than choosing a favorable duration. Then study the difference between strict competitive bounds, additive constants, and expected guarantees for randomized strategies.

Sources

Primary source consulted: Carnegie Mellon University, Online Algorithms lecture notes, https://www.cs.cmu.edu/~15850/notes/lec26.pdf . The rental prices, full duration case analysis, and fictional resource-allocation case are original teaching examples with explicit model assumptions.

Previous: Competitive learning Next: Compiled Query