Randomized, Parallel and Approximation Algorithms

Introduction

Many algorithmic problems cannot be solved efficiently by a single deterministic, exact procedure. A randomized algorithm may use random choices to obtain excellent expected performance or a small probability of error. A parallel algorithm divides work among processors to reduce elapsed time. An approximation algorithm deliberately returns a near-optimal solution when computing the exact optimum is computationally impractical. These approaches are increasingly important in web services, cloud computing, large-scale analytics, cybersecurity, machine learning, and distributed systems.

The three approaches address different constraints. Randomization manages uncertainty and adversarial inputs; parallelism manages elapsed time and throughput; approximation manages computational or memory limits. They can also be combined. For example, a distributed recommendation system may use randomized sampling, process partitions in parallel, and return an approximate ranking within a strict latency budget.

This chapter develops the principles, analysis methods, implementation issues, and trade-offs associated with these algorithms.

Learning Objectives

After studying this chapter, you should be able to:

1. Distinguish Las Vegas and Monte Carlo randomized algorithms.
2. Analyse expected running time, error probability, and amplification.
3. Explain approximation ratios and apply them to optimization problems.
4. Describe sampling, streaming sketches, and probabilistic data structures.
5. Identify parallel decomposition strategies and sources of parallel overhead.
6. Explain distributed computation, consistency, communication, and fault tolerance.
7. Evaluate trade-offs among latency, throughput, memory, accuracy, cost, and reliability.
8. Select an appropriate algorithmic strategy for a practical system.

1. Randomized Algorithms

A randomized algorithm receives a random sequence in addition to its ordinary input. Its behaviour, running time, or output may therefore vary between executions. Randomness is usually generated using a pseudorandom generator; practical implementations must seed and use it carefully, although theoretical analyses commonly assume independent uniformly distributed random bits.

Randomization is useful for three major reasons:

• It can prevent an adversary from reliably constructing a bad input.
• It can simplify an algorithm whose deterministic version is complicated.
• It can provide fast approximate answers for large data sets.

1.1 Las Vegas and Monte Carlo algorithms

A Las Vegas algorithm always returns a correct answer, but its running time is random. Randomized quicksort is a standard example: choosing a random pivot preserves correctness, while the running time depends on the resulting partitions.

A Monte Carlo algorithm has a bounded or predictable running time, but may return an incorrect answer or an approximate answer. A primality test that occasionally reports a probable prime is an example. The error probability is normally designed to be very small.

For a randomized running time T, the expected running time is

where t ranges over possible running times. Expected time is not a promise that every execution is fast: a small number of very slow executions may exist. Engineers should therefore also consider variance, tail probability, and percentile latency.

1.2 Randomized quicksort

Quicksort selects a pivot, partitions the array into smaller and larger elements, and recursively sorts both parts. If the pivot is selected uniformly at random, every element is equally likely to become the pivot. The expected running time is O(n log n), although the worst case remains O(n²).

The expected number of comparisons can be expressed as

where Cₙ is the number of comparisons, and Hₙ = 1 + 1/2 + ⋯ + 1/n is the nth harmonic number. Since Hₙ = Θ(log n), the expected comparison count is Θ(n log n). The formula assumes distinct keys and uniformly random pivot selection.

Randomization does not eliminate the worst-case input for a fixed random sequence; instead, it makes it difficult for an input chosen independently of the random choices to cause consistently poor partitions. If an attacker observes the choices, additional protections such as fresh randomness or a cryptographically secure generator may be necessary.

1.3 Probability of error and amplification

Suppose a Monte Carlo algorithm has error probability p in one independent run. If the algorithm is repeated k times and the results are combined by majority vote, the probability of majority error decreases rapidly when each run is correct with probability greater than 1/2. A simple and widely used bound is obtained from independent repetitions with one-sided error: if an error occurs only when all k trials fail, then

This formula applies only to the stated one-sided-error setting. For example, if p = 0.01 and k = 3, then p³ = 0.000001, or 10⁻⁶. Repetition increases computation and possibly energy use, so it is justified only when the reliability benefit is worth the cost.

For two-sided error, majority voting is commonly analysed using concentration inequalities. If X₁, …, Xₖ are independent Bernoulli variables with mean μ and sample average X̄, Hoeffding’s inequality states that

for ε > 0. The variables must be independent and bounded in [0, 1]. This bound shows that the number of samples needed for a fixed accuracy and confidence grows approximately as 1/ε².

1.4 Random sampling

For a population of size N, a uniformly selected sample estimates a population property. If sampling is with replacement and each observation is represented by an independent variable Xᵢ in [0, 1], the sample mean is

Its expected value equals the population mean under uniform sampling. Sampling without replacement can reduce variance, but independence-based formulas must then be adjusted because observations are dependent.

Sampling is used for estimating query results, testing software, monitoring logs, and building training data. Bias is a major danger: a large sample is not useful if it systematically excludes relevant cases. Examples include surveying only active users or training a classifier on data from one geographic region.

1.5 Sketches and probabilistic data structures

A sketch stores a compact summary rather than the entire data set. It usually sacrifices exactness for memory efficiency and speed.

• A Bloom filter tests set membership. It has no false negatives under standard insertion and query rules, but may have false positives.
• A count-min sketch estimates frequencies. It generally overestimates counts because counters receive contributions from hash collisions.
• HyperLogLog estimates the number of distinct elements using a small amount of memory.
• Reservoir sampling maintains a uniform sample of a stream whose length is unknown in advance.

For a Bloom filter with m bits, k hash functions, and n inserted items, the approximate false-positive probability is

This assumes approximately independent, uniform hash functions and a conventional Bloom-filter construction. The value of k that minimizes this approximation is approximately

The formula is an engineering estimate rather than an exact guarantee. A Bloom filter cannot remove an item individually; deletion requires a counting Bloom filter or a different structure.

2. Approximation Algorithms

An optimization problem asks for the best feasible solution according to an objective function. Exact optimization may be NP-hard, meaning that no polynomial-time algorithm is known for all instances. An approximation algorithm produces a feasible solution with a provable relationship to the optimum.

For a minimization problem, an algorithm has approximation ratio ρ ≥ 1 if, for every input I,

For a maximization problem, the usual guarantee is

where A(I) is the algorithm’s solution and OPT(I) is the optimal value. Some texts instead state a maximization factor α ≤ 1, where value(A(I)) ≥ αOPT(I). The convention must be identified to avoid confusion.

An approximation ratio is a worst-case guarantee. Average practical performance may be much better, but empirical performance cannot replace a proof when a contractual or safety guarantee is required.

2.1 Greedy set cover

In set cover, a universe U must be covered by a collection of subsets. The greedy algorithm repeatedly chooses the set covering the largest number of currently uncovered elements, or, in a weighted version, the best coverage per unit cost.

For the unweighted problem, greedy set cover achieves an approximation ratio at most Hₙ, where n = |U| and Hₙ ≤ 1 + ln n. Thus its solution contains at most Hₙ times as many sets as an optimum solution. The algorithm is efficient and often effective, but exact set cover is computationally difficult.

The proof uses a charging argument: each newly covered element is charged a fraction of the selected set’s cost, and the harmonic series bounds the total charge relative to an optimal cover.

2.2 Vertex cover and a 2-approximation

For the minimum vertex-cover problem, choose an uncovered edge (u, v), add both endpoints to the cover, and remove all edges incident to either endpoint. Every selected edge is disjoint from every other selected edge, so the selected edges form a matching. Any vertex cover must contain at least one endpoint of each matching edge. If M is the matching and C is the algorithm’s cover,

Therefore |C| ≤ 2OPT. This is a 2-approximation. The method is simple, fast, and useful when an exact cover is unnecessary, but its worst-case guarantee is weaker than the optimum possible for some special graph classes.

2.3 Travelling salesperson problem

The metric travelling salesperson problem satisfies the triangle inequality: the direct distance from u to w is no greater than travelling through v. A minimum spanning tree followed by a shortcutting traversal gives a 2-approximation for the metric version. Shortcutting does not increase distance because of the triangle inequality.

Without the metric assumption, the same argument fails. This illustrates an essential principle: an approximation guarantee depends on problem assumptions. Applying an algorithm outside those assumptions may produce no meaningful bound.

2.4 Approximation schemes

A polynomial-time approximation scheme (PTAS) accepts an accuracy parameter ε > 0 and returns a solution within a factor 1 + ε for minimization problems, or at least 1 − ε of optimum for maximization problems. Its running time is polynomial in input size for every fixed ε, but may grow rapidly as ε becomes small.

A fully polynomial-time approximation scheme (FPTAS) is polynomial in both input size and 1/ε. The distinction matters in practice: demanding twice as much precision can increase the computation substantially. Approximation schemes are valuable when the business can express an acceptable accuracy-cost trade-off.

3. Parallel Algorithms

A parallel algorithm divides a problem into tasks that can execute simultaneously. Important measures include:

• Work W(n): total operations performed by all processors.
• Span S(n): length of the longest dependency chain, also called critical-path length.
• Parallelism: W(n)/S(n), the maximum theoretical average concurrency.
• Cost: often pTₚ(n), where p is the number of processors and Tₚ is parallel elapsed time.

A work-efficient algorithm usually has W(n) close to the best sequential work. A highly parallel but work-inefficient method can reduce elapsed time on many processors while wasting energy and money.

Amdahl’s law states that if fraction s of a program is inherently serial and the remainder can be perfectly parallelized across p processors, the speedup is

Here 0 ≤ s ≤ 1. As p approaches infinity, speedup approaches 1/s. The formula assumes no communication, scheduling, memory, or synchronization overhead, so real speedup is lower.

Gustafson’s law considers scaled workloads and is often more realistic for large systems:

It assumes the parallel portion grows with the number of processors while the serial portion remains fixed. The two laws answer different questions: Amdahl’s law asks about a fixed workload; Gustafson’s law asks what larger workload can be handled in a similar time.

3.1 Decomposition patterns

Common patterns include:

• Data parallelism: apply the same operation to independent data partitions, as in map-reduce.
• Task parallelism: execute different functions concurrently.
• Divide and conquer: recursively split, solve, and combine.
• Pipeline parallelism: process successive stages concurrently, improving throughput.
• Graph partitioning: assign subgraphs while minimizing cross-partition communication.

Parallel algorithms must manage load balance. If one worker receives much more work than others, the system’s elapsed time is determined by that worker. Dynamic scheduling can improve balance but adds coordination overhead and may reduce reproducibility.

3.2 Reduction and prefix computation

A reduction combines values using an associative operation, such as addition or maximum. A sequential sum has span O(n), whereas a balanced tree reduction has span O(log n) and work O(n). Associativity is required for arbitrary regrouping; floating-point addition is not perfectly associative, so parallel results may differ slightly from sequential results.

Prefix sums, or scans, compute cumulative values. They support stream compaction, indexing, radix sort, and graph algorithms. A work-efficient parallel scan has O(n) work and O(log n) span under standard parallel-machine assumptions.

4. Distributed Computation

Parallel computation often occurs within one shared-memory machine. Distributed computation uses multiple machines connected by a network, with independent memories and possible failures. Network latency, bandwidth, serialization, partial failure, clock differences, and data consistency become central algorithmic concerns.

In a distributed data-processing framework, a typical workflow is:

1. Partition input data across workers.
2. Execute local computation.
3. Shuffle or exchange intermediate data.
4. Aggregate results.
5. Replicate or persist outputs.

The shuffle can dominate runtime because it consumes network bandwidth and creates synchronization barriers. Data locality, partitioning by key, compression, and combining partial results can reduce this cost.

A useful approximate time model is

The terms are not necessarily independent, and T_failure represents expected recovery or recomputation cost. The model is a planning framework, not a universal physical law.

4.1 Map-reduce and aggregation

Map-reduce separates per-record transformation from grouped aggregation. For example, a web-log system can map each record to (URL, 1), shuffle by URL, and reduce each group by summing counts. Associative and commutative aggregation enables local combiners, which reduce network traffic.

For large numeric aggregates, local partial sums followed by a tree reduction improve scalability. For non-associative operations, the grouping order can change the result, especially with floating-point arithmetic; reproducibility requirements should therefore be specified explicitly.

4.2 Fault tolerance

A distributed algorithm should assume that machines, disks, processes, and network links can fail. Replication, checkpointing, deterministic recomputation, quorum protocols, and idempotent operations are common techniques.

If independent replicas each fail during a time interval with probability q, and all r replicas must fail for data to be unavailable, the idealized unavailability probability is qʳ. This assumes independent failures, which is often unrealistic because power, software, or network faults may be correlated. Geographic diversity and failure-domain awareness are therefore important.

Exactly-once processing is difficult in the presence of retries. Practical systems often achieve at-least-once delivery and use idempotent writes, unique event identifiers, or transactional sinks to prevent duplicate effects.

5. Evaluating Trade-offs

Algorithm selection should not be based on asymptotic time alone. The relevant objective may combine several dimensions:

Latency and throughput are not identical. Batching can increase throughput but delay individual requests. Replication can reduce latency and improve availability but increases storage and write cost. Approximation can reduce memory and computation but may affect fairness or business decisions.

A useful engineering process is:

1. Define correctness, accuracy, and failure requirements.
2. Identify input size, update rate, and workload distribution.
3. Establish a baseline exact or sequential method.
4. Select randomization, approximation, or parallelism only where it addresses a measured bottleneck.
5. Prove or document error and performance bounds.
6. Benchmark typical, worst-case, and adversarial workloads.
7. Monitor drift, tail latency, failures, and approximation error in production.

6. Case Study: Approximate Real-Time Site Analytics

The following is an illustrative case study.

Background

A retail platform receives 500 million page-view events daily. Product managers need hourly counts of distinct visitors and top search terms. Storing every event for repeated exact queries is expensive, and results must be available within two minutes.

Problem

An exact distinct-count query requires retaining visitor identifiers or maintaining a large distributed set. Exact top-term computation requires substantial memory and network traffic. The system also must tolerate worker failures and avoid exposing raw identifiers unnecessarily.

Analysis

The business accepts a distinct-count relative error of approximately 2% and can tolerate small frequency errors for low-volume search terms. It requires much greater accuracy for the top 100 terms. The workload is naturally partitioned by time window and event source.

Approach and solution

Each ingestion worker performs local aggregation. A HyperLogLog sketch estimates distinct visitors for each hour, while a count-min sketch estimates term frequencies. Periodic merges combine sketches from workers. These structures are compact and mergeable, making them suitable for distributed computation.

The system uses three stages: parallel ingestion, local sketch updates, and a tree-based merge. Checkpoints are written to durable storage. Events carry unique identifiers, and writes are idempotent so that a retried batch does not double-count records in the durable event ledger. A small exact table stores the most frequent terms after a candidate-selection stage, improving accuracy for the final top-100 report.

Outcome

The design reduces network traffic because workers send sketches rather than raw events. It meets the reporting deadline under normal load and continues after individual worker failures through checkpoint recovery. Its output is not exact, so the dashboard displays the error policy and timestamp. An offline audit compares sketch estimates with exact counts on sampled windows.

Learning points

1. Mergeability is a major requirement for distributed summaries.
2. Approximation must be stated as an operational error budget, not merely as a theoretical claim.
3. Hybrid designs can reserve exact computation for high-value results.
4. Monitoring is necessary because hash quality, traffic distribution, and implementation bugs can affect estimates.
5. Privacy risk is reduced by limiting raw-data retention, but sketches are not automatically private; membership and frequency leakage must still be assessed.

7. Limitations, Ethics, and Governance

Randomized and approximate systems can produce incorrect or biased outputs. A false negative in a security filter, a false positive in fraud detection, or an inaccurate medical-risk estimate can impose unequal harm. Error rates should therefore be measured across relevant subgroups, not only in aggregate.

Random seeds, hash functions, sampling frames, and approximation parameters should be documented. Reproducible experiments require recorded software versions, seeds where appropriate, input snapshots, and hardware conditions. Cryptographic applications require cryptographically secure randomness; ordinary pseudorandom generators are not sufficient for secrets or authentication tokens.

Privacy-preserving sampling and aggregation should follow data-minimization principles. Differential privacy may add calibrated noise to statistics, but it introduces an explicit accuracy-privacy trade-off and requires careful accounting of the privacy budget. Approximate outputs should not be presented as exact, and user interfaces should communicate uncertainty when decisions depend on estimates.

8. Contemporary Practice and Best Practices

Modern systems combine CPUs, GPUs, vector instructions, serverless workers, and distributed storage. GPUs are effective for regular data-parallel operations but may perform poorly on branch-heavy or irregular graph workloads. Serverless execution can provide elasticity, yet cold starts, invocation limits, and data-transfer costs affect latency.

Best practices include:

• Use a secure and well-tested source of randomness when adversaries are relevant.
• Separate statistical error from implementation error.
• State approximation assumptions and confidence levels.
• Prefer work-efficient parallel algorithms.
• Measure p50, p95, and p99 latency rather than only averages.
• Minimize synchronization and network shuffles.
• Use idempotence and checkpointing for distributed retries.
• Test skewed, adversarial, and failure-heavy workloads.
• Validate estimates against exact results on sampled data.
• Expose accuracy, freshness, and failure status to downstream users.

Chapter Summary

Randomized algorithms use random choices to improve expected performance, simplify design, or estimate large-scale properties. Las Vegas algorithms always produce correct answers but have random running time; Monte Carlo algorithms bound time while allowing a controlled probability of error. Repetition, concentration bounds, sampling, Bloom filters, and sketches provide practical methods for managing uncertainty.

Approximation algorithms trade exact optimality for efficiency and provide formal ratios such as 2-approximation for vertex cover or Hₙ-approximation for greedy set cover. Their guarantees depend on clearly stated assumptions. Parallel algorithms reduce elapsed time through decomposition, but work, span, communication, synchronization, and load balance determine actual performance. Amdahl’s and Gustafson’s laws provide complementary views of scalability.

Distributed computation adds network cost, independent failures, consistency concerns, and recovery requirements. Effective designs combine partitioning, local aggregation, mergeable summaries, replication, checkpointing, and idempotent operations. Professional algorithm selection must balance latency, throughput, memory, accuracy, cost, fault tolerance, privacy, and fairness rather than optimizing only asymptotic running time.

Key Terms

Randomized algorithm: An algorithm whose behaviour depends partly on random choices.

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

Monte Carlo algorithm: A randomized algorithm with a bounded or predictable runtime and a probability of error.

Expected running time: The probability-weighted average running time over random choices.

Amplification: Repeating a randomized algorithm to reduce its error probability.

Sampling: Selecting observations to estimate properties of a larger population or stream.

Sketch: A compact probabilistic summary of data.

Bloom filter: A space-efficient membership structure with possible false positives.

Approximation ratio: A worst-case bound comparing an algorithmic solution with an optimum solution.

PTAS: A polynomial-time approximation scheme parameterized by an accuracy value.

FPTAS: An approximation scheme polynomial in both input size and the inverse accuracy parameter.

Work: Total operations performed by all parallel workers.

Span: Length of the longest dependency chain in a parallel computation.

Amdahl’s law: A model showing how a serial fraction limits speedup for a fixed workload.

Data parallelism: Applying the same operation concurrently to independent data items.

Reduction: Combining many values using an associative operation.

Distributed computation: Computation across machines with separate memories connected by a network.

Idempotence: A property whereby repeating an operation has the same effect as performing it once.

Tail latency: High-percentile response time, such as p95 or p99 latency.

Review Questions

Short Answer Questions

1. What is the difference between a Las Vegas and a Monte Carlo algorithm?
2. Why does a Bloom filter permit false positives but not false negatives under standard operation?
3. Define the approximation ratio for a minimization problem.
4. Distinguish work from span in parallel computation.
5. Why are idempotent operations useful in distributed systems?

Long Answer Questions

1. Explain randomized quicksort and why its expected running time is O(n log n), despite an O(n²) worst case.
2. Describe greedy set cover and explain the significance of its Hₙ approximation guarantee.
3. Compare Amdahl’s law and Gustafson’s law, including the workloads each model assumes.
4. Explain how sketches support scalable distributed analytics and identify their principal accuracy limitations.
5. Discuss the relationship among communication, synchronization, partitioning, and fault tolerance in distributed computation.

Analytical / Application Questions

1. A Monte Carlo algorithm has one-run error probability 0.02, and failures are independent and one-sided. What is the error probability after four repetitions if all four results must fail for the combined method to fail? Explain whether the additional computation is justified for a safety-critical application.
2. A team proposes a parallel design that has a serial fraction of 0.10 and uses 20 processors. Use Amdahl’s law to calculate the ideal speedup, then explain why the measured speedup will probably be lower.
3. A product team wants exact daily unique-user counts but has a strict memory budget and accepts 2% estimation error. Recommend an algorithmic architecture, identify its assumptions, and explain how you would validate accuracy and monitor failures.

Multiple Choice Questions with Answers

Question 1

Which statement correctly describes a Las Vegas randomized algorithm?

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

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

C. It uses no random choices during execution.

D. It guarantees an exact answer only on average.

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

Question 2

A one-sided-error algorithm has error probability p = 0.01 per independent run. If four runs fail simultaneously are required for combined failure, what is the error probability?

A. 0.04

B. 0.0004

C. 0.00000001

D. 0.25

Correct Answer: C. 0.00000001

Question 3

For a minimization problem, which inequality expresses a ρ-approximation guarantee?

A. cost(A) ≥ ρOPT

B. cost(A) ≤ ρOPT

C. cost(A) = OPT − ρ

D. cost(A) ≤ OPT/ρ for every ρ ≥ 1

Correct Answer: B. cost(A) ≤ ρOPT

Question 4

What is the standard worst-case approximation ratio of the simple maximal-matching algorithm for minimum vertex cover?

A. 1/2

B. 1

C. 2

D. log n only

Correct Answer: C. 2

Question 5

Which condition is essential for a balanced tree reduction to regroup operations without changing their mathematical meaning?

A. The operation must be associative.

B. The operation must always be subtraction.

C. The input must contain distinct values.

D. Every processor must have identical cache size.

Correct Answer: A. The operation must be associative.

Question 6

A program has serial fraction s = 0.10. Under ideal Amdahl conditions, what is the limiting speedup as the processor count approaches infinity?

A. 0.10

B. 1.10

C. 9

D. 10

Correct Answer: D. 10

Question 7

Which statement about a standard Bloom filter is correct?

A. It supports exact deletion without additional structure.

B. It can produce false positives but not false negatives for inserted items.

C. It stores every inserted key explicitly.

D. Its false-positive probability is independent of the number of inserted items.

Correct Answer: B. It can produce false positives but not false negatives for inserted items.

Question 8

Why are local combiners useful in a map-reduce aggregation?

A. They eliminate the need for any partitioning.

B. They reduce intermediate data sent over the network.

C. They guarantee zero worker failures.

D. They make every operation non-associative.

Correct Answer: B. They reduce intermediate data sent over the network.

Question 9

Which metric describes the longest dependency chain in a parallel computation?

A. Work

B. Throughput

C. Span

D. Replication factor

Correct Answer: C. Span

Question 10

Which design best supports safe retries in an at-least-once distributed processing system?

A. Non-idempotent writes with no event identifiers

B. Idempotent operations using unique event identifiers

C. Disabling all checkpoints

D. Sending every event to one unreplicated worker

Correct Answer: B. Idempotent operations using unique event identifiers