Randomized, Approximation and Online Algorithms

Introduction

Many computational problems encountered in practice have one or more of three difficult characteristics. First, the input may be uncertain, adversarial, or too large to inspect completely. Second, an exact optimum may require exponential time or may be computationally intractable. Third, decisions may have to be made before the future is known. Randomized, approximation, streaming, and online algorithms address these difficulties by relaxing one or more conventional assumptions of algorithm design.

A randomized algorithm uses random choices during execution. An approximation algorithm deliberately returns a solution that may not be optimal but is guaranteed to be close to optimal, or performs well empirically. An online algorithm processes requests sequentially and must make decisions without knowing future requests. Streaming algorithms operate with severe memory constraints, often examining each item only once. These approaches are central to distributed systems, network routing, cloud computing, cybersecurity, recommendation systems, large-scale data analytics, and operations research.

The key intellectual issue is not simply speed. It is the disciplined management of uncertainty and compromise: what is randomized, what guarantee is obtained, against which benchmark performance is measured, and under which assumptions the guarantee holds.

Learning Objectives

By the end of this chapter, students should be able to:

1. Distinguish Las Vegas and Monte Carlo randomized algorithms.
2. Use expectation, probability bounds, and concentration inequalities to analyze randomized performance.
3. Explain approximation ratios and design approximation algorithms for difficult optimization problems.
4. Apply competitive analysis to online algorithms.
5. Describe streaming models and estimate quantities under strict memory limits.
6. Evaluate trade-offs among accuracy, runtime, memory, robustness, and implementation complexity.
7. Select an appropriate algorithmic paradigm for a large-scale or uncertain application.

1. Randomized Algorithmic Models

A deterministic algorithm maps an input to a fixed sequence of operations. A randomized algorithm additionally accesses a source of random bits. For a fixed input x, its running time and output are therefore random variables.

Randomization can provide three important benefits:

• Expected efficiency: an algorithm may be fast on average even when some executions are slow.
• Simplicity: random choices can avoid complicated deterministic case analyses.
• Robustness: randomization can make it difficult for an adversary to construct a consistently bad input sequence.

The probability space must be stated carefully. Usually, the input is fixed and probability is taken over the algorithm’s internal random bits. In other settings, both input and algorithm may be random. These interpretations must not be confused.

Las Vegas and Monte Carlo Algorithms

A Las Vegas algorithm always returns a correct answer, but its running time is random. A Monte Carlo algorithm has a bounded or predictable running time, but may return an incorrect answer with small probability.

For a Las Vegas algorithm with running time T, the expected runtime is

where t ranges over possible running times. Correctness is unconditional, but the expectation is meaningful only relative to a specified random-choice model.

For a Monte Carlo algorithm, if E is the event of an incorrect answer, its error probability is

where δ is the permitted error level. If independent repetitions are available, repeating a procedure can reduce error. For a one-sided test whose false-positive probability is at most p in one trial, k independent repetitions give

This assumes independence and the same bound p for each trial. Repetition is not automatically valid when trials share correlated randomness or data-dependent state.

Randomized Quicksort

Randomized quicksort chooses a pivot uniformly from the current subarray. The partition operation takes Θ(n) time, while the expected total time is Θ(n log n). Randomization does not change the worst-case possibility of Θ(n²), because an unlucky sequence of pivots can repeatedly produce highly unbalanced partitions. However, for every fixed input permutation, the expected running time over random pivot choices is Θ(n log n).

A useful analysis counts comparisons. For sorted elements with ranks i and j, where i < j, they are compared only if one of them is selected as the first pivot from the set of elements with ranks i through j. Thus,

The expected number of comparisons is therefore

The argument illustrates a general technique: express total cost as a sum of indicator random variables and use linearity of expectation.

Indicators and Linearity of Expectation

For an event A, define its indicator variable I_A as 1 when A occurs and 0 otherwise. Then

If X is the total cost of several events, represented by indicators I₁, …, Iₘ,

Linearity of expectation does not require the indicators to be independent. This makes it especially powerful in randomized algorithm analysis.

2. Probabilistic Bounds and Concentration

An expected value alone may conceal significant variability. A system with expected latency of 10 milliseconds may be unacceptable if one execution in a hundred takes several seconds. Tail bounds quantify the probability of large deviations.

Markov’s Inequality

If X is a nonnegative random variable and a > 0, then

Markov’s inequality requires only nonnegativity, so it is broadly applicable but often loose.

Chebyshev’s Inequality

If X has mean μ and variance σ², then for k > 0,

It requires finite variance and does not require a particular distribution. The bound is usually stronger than Markov’s when variance is known.

Chernoff Bounds

For a sum X of independent Bernoulli random variables with mean μ, a standard multiplicative Chernoff bound is, for 0 < δ < 1,

and

The constants shown are common simplified forms. The assumptions—independence, Bernoulli summands, and the stated range of δ—must be respected. Chernoff bounds explain why randomized load balancing and sampling can be highly reliable when the number of independent trials is large.

High-Probability Statements

An algorithm runs in O(f(n)) time with high probability if, under a stated random model, the probability that its runtime exceeds a constant multiple of f(n) decreases sufficiently rapidly with n. The phrase is not universal: some authors mean probability at least 1 − 1/n, while others mean 1 − 1/nᶜ for a fixed c > 0. A rigorous statement specifies the exact failure probability.

3. Approximation Algorithms

Many optimization problems are NP-hard, meaning that no polynomial-time exact algorithm is known and such an algorithm would imply P = NP. An approximation algorithm computes a feasible solution efficiently and provides a bound relative to the optimum.

For a minimization problem, let A(I) be the algorithm’s solution cost and OPT(I) the optimal cost for instance I. An algorithm is an α-approximation if

For a maximization problem, the usual guarantee is

Some literature instead states a maximization factor ρ ≤ 1, with A(I) ≥ ρOPT(I). The convention must be identified before comparing results.

Approximation ratio is a worst-case guarantee. It does not mean that every practical instance is close to the bound, and it is distinct from average-case performance.

Approximation Design Strategies

Common strategies include:

1. Greedy selection: repeatedly choose the locally most beneficial feasible action.
2. Relaxation and rounding: solve a polynomial-time relaxation, often linear programming, then convert the fractional solution into an integral one.
3. Primal–dual methods: construct a feasible primal solution and a dual certificate whose values establish a ratio.
4. Local search: repeatedly improve a solution until no permitted local change helps.
5. Randomized rounding: interpret fractional values as probabilities and round while controlling expected cost.
6. Parameterized or restricted exact methods: exploit special structure such as bounded treewidth or small parameter values.

Vertex Cover: A 2-Approximation

Given an undirected graph G = (V, E), a vertex cover is a subset C ⊆ V such that every edge has at least one endpoint in C. The objective is to minimize |C|.

A simple algorithm repeatedly selects an uncovered edge (u, v), places both endpoints in C, and deletes all edges incident to u or v. The selected edges form a matching because all incident edges are deleted. If M is the resulting matching, every vertex cover must contain at least one endpoint of every edge in M. Therefore,

The algorithm selects two vertices per matching edge, so |C| = 2|M|. Consequently,

This is a 2-approximation. The proof demonstrates a general approximation pattern: construct a lower bound on OPT and compare the algorithm’s cost with that bound.

Set Cover and the Harmonic Guarantee

In Set Cover, a universe U must be covered using a collection of subsets with minimum total cost. The greedy algorithm repeatedly chooses the set covering the largest number of currently uncovered elements per unit cost. For unit costs, its approximation ratio is at most Hₙ, where n = |U| and

The ratio is logarithmic, not constant. This distinction matters for large universes and for claims about scalability.

Approximation Schemes

A polynomial-time approximation scheme (PTAS) accepts ε > 0 and returns a solution within a factor 1 + ε for minimization problems, with polynomial runtime in n for every fixed ε. The polynomial’s degree may depend on 1/ε. A fully polynomial-time approximation scheme (FPTAS) is polynomial in both n and 1/ε.

Approximation schemes therefore offer a controllable accuracy–runtime trade-off, but their existence is problem-specific. A PTAS is not necessarily practical when ε is very small.

4. Online Algorithms and Competitive Analysis

An online algorithm receives a sequence of requests σ = (r₁, r₂, …, rₙ) and must act on rᵢ before seeing rᵢ₊₁, …, rₙ. The corresponding offline optimum knows the entire sequence in advance.

For a minimization problem, an online algorithm A is c-competitive if there exists an additive constant b such that, for every input sequence σ,

The constant c is the competitive ratio. For maximization, the inequality is typically reversed in the equivalent factor form. The additive constant handles small instances and is often omitted asymptotically.

Competitive analysis is deliberately adversarial. It asks how the algorithm performs relative to an omniscient optimum on the worst possible sequence. It does not assume a probability distribution over requests.

Paging and the Marking Algorithm

In the paging problem, a cache holds k pages. A request for a page not in cache causes a fault; if the cache is full, a page must be evicted. The offline optimum knows future requests.

The deterministic least-recently-used (LRU) policy is k-competitive. A classical lower bound shows that no deterministic online paging algorithm can achieve a competitive ratio smaller than k in the worst case. Randomized algorithms can improve this ratio against an oblivious adversary, but the precise guarantee depends on the algorithm and adversary model.

The adversary model is crucial. An oblivious adversary fixes the request sequence independently of the algorithm’s random choices. An adaptive adversary may observe actions and react. Randomized guarantees against adaptive adversaries require stronger care, often through conditional expectations or specially designed randomization.

Ski-Rental Model

In ski rental, renting costs r per day and buying costs B once. The future number of skiing days is unknown. A deterministic strategy rents for B/r days and then buys, giving a competitive ratio approaching 2. If the season ends just before purchase, the algorithm pays nearly 2B while the optimum rents for nearly B. If it continues, the algorithm pays at most B extra compared with buying immediately.

This model captures decisions involving an irreversible investment under uncertain demand, such as cloud reservation, equipment leasing, or storage provisioning.

5. Streaming Algorithms

A streaming algorithm processes a sequence a₁, a₂, …, aₙ using memory much smaller than n, often in one pass. The principal resource measures are:

• Passes: number of scans over the stream.
• Working memory: space excluding the input stream.
• Update time: processing time per item.
• Accuracy: additive or multiplicative error.
• Failure probability: probability that the estimate violates its guarantee.

A streaming estimate should specify all five dimensions where relevant.

Sampling for Mean Estimation

Suppose X₁, …, Xₙ are values in [0, 1]. A uniform sample of s positions, with replacement, produces sample mean

If the samples are independent, Hoeffding’s inequality gives

where μ is the population mean and 0 < ε < 1. To ensure failure probability at most δ, it suffices that

This bound is independent of n, a major advantage for streams. It assumes independent uniform sampling and bounded values. For an unbounded or heavily weighted stream, another estimator or normalization is required.

Reservoir Sampling

Reservoir sampling maintains a uniform sample of size k from a stream whose final length is unknown. The algorithm stores the first k items. When item i > k arrives, it is selected with probability k/i; if selected, it replaces a uniformly chosen reservoir item. After processing i items, each item has probability k/i of being in the reservoir. This invariant proves uniformity by induction.

Frequency Estimation and Sketches

Exact frequency tables may require space proportional to the number of distinct keys. Sketches use compact arrays and hash functions to estimate frequencies. Examples include Count-Min Sketch for approximate point queries and HyperLogLog for distinct-count estimation.

A Count-Min Sketch with width w and depth d uses d arrays of w counters. Each update increments one counter in every row. A query returns the minimum of the corresponding counters. With suitable pairwise-independent hash functions, the estimate never underestimates a nonnegative frequency, while the overestimate can be bounded with probability at least 1 − δ by choosing dimensions related to ε and δ. Hash independence and counter overflow are practical concerns.

6. A Unified Applied Case: Capacity Planning for a Cloud Service

The following is an illustrative case, not a report of a particular company.

Background

A cloud platform hosts thousands of customer services. Request rates fluctuate rapidly, and the platform must decide how many virtual machines to reserve, when to buy long-term capacity, and how to route incoming requests.

Problem

Exact optimization is computationally expensive because the platform must account for uncertain demand, placement constraints, service-level objectives, and changing prices. The system also receives telemetry as a high-volume stream and cannot retain every event.

Analysis

Three decision timescales are identified:

1. Milliseconds: route each request without knowing future arrivals.
2. Minutes: estimate current demand and detect heavy users from a stream.
3. Days or weeks: choose capacity commitments under uncertain demand.

The routing component is online. The telemetry component is streaming. Capacity placement is modeled as a difficult combinatorial optimization problem. Randomized exploration is used to avoid systematic concentration on a small set of machines.

Approach and Solution

• A randomized load-balancing policy samples a small set of machines and sends a request to the least-loaded sampled machine. This reduces communication overhead while retaining strong load-balancing behavior.
• Reservoir sampling maintains representative samples of requests for diagnostic analysis.
• A Count-Min Sketch identifies high-frequency customer keys using bounded memory.
• A greedy or linear-programming-based approximation method assigns workloads to machines. The system records the approximation factor and resource constraints rather than presenting the result as optimal.
• A ski-rental-style policy compares on-demand rental with reserved capacity. The policy is evaluated using competitive analysis and historical traces.
• Monte Carlo simulation estimates the probability of violating service-level objectives under candidate policies. Independent seeds and confidence intervals are used to avoid treating a single simulation run as proof.

Outcome

The architecture reduces memory and decision latency while providing explicit error and quality controls. It does not guarantee that every practical outcome is optimal. Instead, it makes the trade-offs auditable: estimated demand has a confidence target, placement has an approximation bound, and online decisions have a benchmark-relative guarantee.

Learning Points

The case illustrates that advanced systems commonly combine paradigms rather than choose only one. Streaming estimates support online decisions; approximation makes large optimization problems tractable; randomization reduces predictable worst cases; and simulation evaluates risks that formal analysis may not fully capture.

7. Limitations, Governance, and Best Practices

Model and Adversary Dependence

A randomized guarantee depends on the source of randomness and adversary model. A distributional assumption that is reasonable in a laboratory may fail under malicious input manipulation. Seeds should be protected when unpredictability matters, but reproducible seeds are valuable for debugging and scientific evaluation.

Approximation Is Not Automatically Safe

A numerical ratio may ignore fairness, latency variance, energy use, or legal constraints. A solution that is within 1.1 of a cost optimum may violate a safety or privacy requirement. Hard constraints must be enforced before applying an approximation objective.

Error Budgets and Reproducibility

For Monte Carlo and streaming systems, specify ε, δ, sampling assumptions, confidence procedures, and the treatment of repeated queries. If many queries are made, a per-query failure probability may not control the probability that at least one query fails. Union bounds or workload-level validation may be necessary.

Online Fairness and Feedback Loops

Online algorithms can reinforce historical patterns. For example, a routing policy that sends more traffic to a machine because it appears reliable may deprive other machines of observations, making the estimate self-confirming. In allocation or recommendation systems, fairness constraints, monitoring, and periodic re-evaluation are essential.

Practical Best Practices

1. State whether guarantees are worst-case, expected, high-probability, or empirical.
2. Define the adversary or data-generation model.
3. Separate approximation error from measurement and implementation error.
4. Report memory, passes, update time, and failure probability for streaming algorithms.
5. Compare online performance with meaningful baselines, including offline lower bounds when available.
6. Test randomized algorithms across multiple seeds and report variability.
7. Preserve hard safety, privacy, and regulatory constraints independently of optimization goals.
8. Use adversarial and distribution-shift testing before deployment.

8. Contemporary Directions

Modern machine-learning systems increasingly use randomized optimization, sketching, approximate nearest-neighbor search, and online learning. Federated and privacy-preserving analytics rely on randomization to limit information leakage, although privacy guarantees require formal mechanisms such as differential privacy rather than informal noise addition. Distributed systems use randomized backoff, gossip, leader election, and load balancing to avoid synchronization and contention.

Research continues on beyond-worst-case analysis, smoothed analysis, adaptive online algorithms, sublinear algorithms, distributed streaming, and algorithms robust to strategic or malicious participants. A major methodological trend is the combination of formal guarantees with data-driven evaluation. Neither theoretical bounds nor benchmarks alone provide a complete assessment.

Chapter Summary

Randomized algorithms use internal random choices to obtain expected efficiency, simplicity, or robustness. Las Vegas algorithms always produce correct answers but have random runtime; Monte Carlo algorithms control runtime while permitting bounded error. Linearity of expectation, Markov’s inequality, Chebyshev’s inequality, and Chernoff bounds provide tools for analyzing expected cost and tail behavior.

Approximation algorithms address computationally difficult optimization problems by producing feasible solutions with a provable relationship to optimum. Greedy methods, relaxations, rounding, primal–dual reasoning, and local search are central design techniques. Vertex Cover has a simple 2-approximation, while Set Cover’s greedy method has a logarithmic harmonic guarantee.

Online algorithms act without future knowledge and are evaluated through competitive analysis against an offline optimum. Paging and ski rental demonstrate how adversarial benchmarks formalize the cost of uncertainty. Streaming algorithms process massive data with limited memory; sampling, reservoir sampling, sketches, and concentration bounds make approximate computation possible.

The appropriate paradigm depends on the application’s uncertainty, scale, constraints, and acceptable error. Professional practice requires explicit assumptions, reproducible experiments, monitoring, fairness and privacy safeguards, and a clear distinction between formal guarantees and empirical performance.

Key Terms

Randomized algorithm: An algorithm whose execution uses random choices.

Las Vegas algorithm: A randomized algorithm that always returns a correct result.

Monte Carlo algorithm: A randomized algorithm with bounded probability of error.

Expected running time: Average running time over the algorithm’s random choices under a specified model.

Indicator variable: A 0–1 variable representing whether an event occurs.

Concentration inequality: A bound on the probability that a random variable deviates from its expectation.

Approximation algorithm: An efficient algorithm that returns a solution near the optimum.

Approximation ratio: A worst-case multiplicative comparison between an algorithm’s solution and OPT.

PTAS: A polynomial-time approximation scheme parameterized by ε.

FPTAS: An approximation scheme polynomial in both input size and 1/ε.

Online algorithm: An algorithm that must decide without seeing future requests.

Competitive ratio: Worst-case comparison of an online algorithm with an offline optimum.

Oblivious adversary: An adversary that fixes the input independently of random choices.

Adaptive adversary: An adversary that can react to observed algorithmic behavior.

Streaming algorithm: An algorithm that processes a sequence using restricted memory.

Reservoir sampling: A method for maintaining a uniform sample from an unknown-length stream.

Sketch: A compact randomized data structure for approximate queries.

Additive error: An estimate differs from the true value by at most ε in absolute terms.

Failure probability: The probability that a randomized guarantee is violated.

Primal–dual method: An approximation technique using feasible primal and dual solutions to establish bounds.

Review Questions

Short Answer Questions

1. What is the fundamental difference between Las Vegas and Monte Carlo algorithms?
2. Why does linearity of expectation remain useful when random variables are dependent?
3. Define the approximation ratio for a minimization problem.
4. What information is unavailable to an online algorithm?
5. What invariant does reservoir sampling maintain?

Long Answer Questions

1. Explain randomized quicksort and derive why its expected number of comparisons is Θ(n log n).
2. Compare Markov, Chebyshev, and Chernoff bounds, including their assumptions and practical uses.
3. Describe the 2-approximation algorithm for Vertex Cover and prove its approximation guarantee.
4. Explain competitive analysis using paging and ski rental as examples.
5. Discuss the architecture and trade-offs of a streaming system that estimates frequencies and means.

Analytical / Application Questions

1. A streaming system samples values in [0, 1] and requires additive error ε = 0.05 with failure probability at most δ = 0.01. Use the stated Hoeffding-based formula to calculate a sufficient sample size and explain its assumptions.
2. Design a cloud-capacity policy combining an online decision rule, a streaming estimator, and an approximation algorithm. State the guarantee or limitation associated with each component.
3. An adversary can observe the actions of a randomized online algorithm and choose future requests accordingly. Explain why a guarantee proved only for an oblivious adversary may fail, and propose experimental tests to investigate the risk.

Multiple Choice Questions with Answers

Question 1

Which statement best describes a Las Vegas algorithm?

A. It always returns a correct answer, but its running time may be random.

B. It always runs in constant time, but may return an incorrect answer.

C. It uses no random bits and has worst-case linear time.

D. It returns an answer only when the input is uniformly distributed.

Correct Answer: A. It always returns a correct answer, but its running time may be random.

Question 2

For independent Bernoulli trials with mean μ, which bound is a standard upper-tail Chernoff form for 0 < δ < 1?

A. Pr[X ≥ (1 + δ)μ] ≤ exp(−μδ²/3)

B. Pr[X ≥ (1 + δ)μ] ≤ μ/(1 + δ)

C. Pr[X ≥ (1 + δ)μ] ≤ 1 − exp(−μδ²/3)

D. Pr[X ≥ (1 + δ)μ] ≤ δ/μ

Correct Answer: A. Pr[X ≥ (1 + δ)μ] ≤ exp(−μδ²/3)

Question 3

A minimization algorithm is an α-approximation when which condition holds for every instance I?

A. A(I) ≥ αOPT(I)

B. A(I) ≤ αOPT(I), with α ≥ 1

C. A(I) = OPT(I) + α

D. A(I) ≤ OPT(I)/α, with α ≥ 1

Correct Answer: B. A(I) ≤ αOPT(I), with α ≥ 1

Question 4

Why does the standard Vertex Cover matching algorithm achieve a factor of 2?

A. It selects one endpoint from every edge and doubles the result.

B. It constructs a matching of size |M|, giving a lower bound OPT ≥ |M|, and selects 2|M| vertices.

C. It solves the exact problem on two disjoint subgraphs.

D. It uses two independent random choices for every vertex.

Correct Answer: B. It constructs a matching of size |M|, giving a lower bound OPT ≥ |M|, and selects 2|M| vertices.

Question 5

What is the defining restriction of an online algorithm?

A. It must use constant memory.

B. It cannot use comparisons.

C. It must make decisions without knowing future requests.

D. It must always be randomized.

Correct Answer: C. It must make decisions without knowing future requests.

Question 6

For a minimization problem, a c-competitive online algorithm generally satisfies which relation?

A. cost_A(σ) ≥ cOPT(σ) for every σ

B. cost_A(σ) ≤ cOPT(σ) + b for every σ

C. cost_A(σ) = OPT(σ) for every σ

D. cost_A(σ) ≤ OPT(σ)/c for every σ

Correct Answer: B. cost_A(σ) ≤ cOPT(σ) + b for every σ

Question 7

Which property does reservoir sampling provide after processing i stream items?

A. The reservoir contains the i most recent items.

B. Each item seen so far has equal probability of being included.

C. The largest k items are always retained.

D. The sample is deterministic and independent of k.

Correct Answer: B. Each item seen so far has equal probability of being included.

Question 8

Using s ≥ ln(2/δ)/(2ε²), what sample size is sufficient for ε = 0.1 and δ = 0.05?

A. Approximately 15

B. Approximately 50

C. Approximately 185

D. Approximately 1,850

Correct Answer: C. Approximately 185

Question 9

Which statement about a Count-Min Sketch for nonnegative frequencies is generally correct?

A. Its point estimate is always less than the true frequency.

B. Its estimate is based on the minimum of hashed counters and typically does not underestimate.

C. It requires storing every distinct key exactly.

D. It provides exact frequencies regardless of width.

Correct Answer: B. Its estimate is based on the minimum of hashed counters and typically does not underestimate.

Question 10

A PTAS for a minimization problem is designed to return a solution within which factor for a chosen ε > 0?

A. 1 − ε

B. ε only

C. 1 + ε

D. 2ε regardless of ε

Correct Answer: C. 1 + ε