The Central Idea
Algorithms differ not only in what problem they solve, but also in what kind of guarantee they provide.
Three broad categories are:
- exact algorithms, which guarantee the correct answer;
- approximation algorithms, which guarantee an answer near the optimum;
- randomized algorithms, which use random choices during execution.
These categories can overlap. A randomized algorithm may still return an exact answer, and an approximation algorithm may be deterministic or randomized.
Exact Algorithms
An exact algorithm always returns a fully correct solution to the stated problem, assuming its preconditions are satisfied.
Examples include:
- binary search on sorted data;
- merge sort;
- Dijkstra's algorithm on nonnegative weighted graphs;
- dynamic programming for many finite optimization problems.
Exact Does Not Mean Fast
An exact algorithm may be mathematically perfect but computationally expensive.
For some problems, the known exact methods may require time such as
\[ O(2^n) \]or
\[ O(n!). \]Exactness and efficiency are separate properties.
Brute-Force Exact Algorithms
A brute-force algorithm may examine every candidate solution and choose the correct or optimal one.
Such an algorithm can be exact because it misses nothing.
The difficulty is that the candidate space may be enormous.
Example: Exact Subset Search
Suppose we want to know whether some subset of \(n\) objects satisfies a required condition.
Examining every subset checks
\[ 2^n \]possibilities.
This is exact, but the running time grows exponentially.
Why Approximation Is Sometimes Useful
In many optimization problems, a near-optimal answer found quickly may be more useful than an exact optimum found too slowly.
Approximation methods deliberately accept some loss in solution quality in exchange for improved computational efficiency.
Approximation Algorithms
An approximation algorithm returns a feasible solution that may not be optimal but comes with a provable quality guarantee.
The guarantee compares the algorithm's solution with the unknown optimum.
Approximation Ratio
Suppose an optimization problem is a minimization problem.
Let
\[ A \]be the cost returned by the approximation algorithm, and let
\[ OPT \]be the optimal cost.
A ratio guarantee may have the form
\[ A\le \rho\,OPT \]for some
\[ \rho\ge1. \]Interpreting a 2-Approximation
For a minimization problem, a 2-approximation guarantees
\[ A\le2\,OPT. \]The returned cost is at most twice the optimal cost.
The algorithm may often do much better, but the guarantee says it will never do worse than that factor.
Approximation for Maximization
For a maximization problem, a common guarantee may be written
\[ A\ge \alpha\,OPT \]where
\[ 0<\alpha\le1. \]For example,
\[ A\ge\frac12OPT \]guarantees at least half the optimal value.
Approximation Guarantee Versus Observed Performance
A theoretical approximation ratio is a worst-case guarantee.
Real instances may produce solutions much closer to optimal.
The guarantee tells us what quality can be promised across all valid inputs, not what happens only on typical examples.
Approximation Is Not the Same as Guessing
A legitimate approximation algorithm should have:
- a precise output definition;
- a feasibility guarantee;
- a provable relationship to the optimum;
- a stated running-time bound.
Approximation is controlled loss of optimality, not arbitrary estimation.
Heuristics
A heuristic is a practical rule intended to produce good solutions quickly.
A heuristic may work very well in practice but may have no formal approximation guarantee.
This distinguishes heuristics from approximation algorithms with proven quality bounds.
Approximation Algorithms Versus Heuristics
The distinction is:
- approximation algorithm: provable quality guarantee;
- heuristic: practical strategy without necessarily having such a guarantee.
Both can be useful, but their claims should not be confused.
Greedy Methods Can Be Exact or Approximate
Greedy structure alone does not determine whether an algorithm is exact.
For interval scheduling, a correct greedy rule gives an exact optimum.
In other optimization problems, a greedy rule may provide only an approximation.
Deterministic Algorithms
A deterministic algorithm follows the same computational path whenever it receives the same input and starts in the same state.
Its choices are completely determined by the input and algorithm rules.
Randomized Algorithms
A randomized algorithm uses random choices as part of its execution.
The same input may therefore produce:
- different execution paths;
- different running times;
- different outputs, depending on the algorithm type.
Randomness Can Improve Algorithm Design
Randomization can help:
- avoid consistently bad deterministic choices;
- simplify algorithms;
- improve expected running time;
- sample very large spaces;
- produce probabilistic guarantees.
Randomized Quicksort Intuition
Quicksort performance depends strongly on pivot choices.
Choosing a pivot randomly reduces the chance that a particular input order consistently causes extremely unbalanced partitions.
The result is a useful expected-performance guarantee across random pivot choices.
Las Vegas Algorithms
A Las Vegas algorithm always returns a correct answer, but its running time may depend on random choices.
Randomness affects
\[ \boxed{\text{how long the algorithm runs}} \]rather than
\[ \boxed{\text{whether the answer is correct}}. \]Monte Carlo Algorithms
A Monte Carlo algorithm runs within a controlled resource bound but may return an incorrect answer with some bounded probability.
Randomness affects correctness probability.
The algorithm is useful when the error probability can be made acceptably small.
Las Vegas Versus Monte Carlo
- Las Vegas: always correct, random running time.
- Monte Carlo: bounded running behavior, small probability of error.
These categories distinguish where randomness enters the guarantee.
One-Sided Error
Some randomized decision algorithms can make an error in only one direction.
For example, an algorithm may:
- never incorrectly reject a true case;
- but occasionally incorrectly accept a false case.
This is called one-sided error.
Two-Sided Error
Other randomized algorithms may err in either direction.
They may occasionally produce:
- a false positive;
- or a false negative.
Their total error probability must be bounded and analyzed.
Error Probability
Suppose a randomized algorithm has probability
\[ p \]of being wrong on one independent run.
If the algorithm is repeated independently, the probability of repeated failure can often decrease rapidly.
Error Reduction by Repetition
Suppose an algorithm has error probability
\[ \frac14 \]on one independent trial.
If all three independent trials must fail for the combined procedure to fail, then the error probability becomes
\[ \left(\frac14\right)^3 = \frac1{64}. \]Amplification
Repeating a randomized algorithm to improve confidence is often called amplification.
More computation is exchanged for a smaller probability of error.
This is another resource tradeoff.
Independence Matters
Multiplying error probabilities such as
\[ p^k \]assumes the relevant trials are independent.
If repeated trials are strongly correlated, the error may not decrease as predicted.
Random Sampling
Randomized algorithms frequently use samples rather than processing an entire large population.
Sampling can reduce computational cost, but results become statistical rather than exact.
Sample size and sampling method affect accuracy and confidence.
Approximation by Sampling
Suppose a quantity is difficult to compute exactly but can be estimated by repeated random experiments.
The average of the sampled outcomes may approach the desired value as the number of trials grows.
This is a central idea in Monte Carlo numerical methods.
Monte Carlo Estimation of \(\pi\)
Consider random points sampled uniformly in the square
\[ [-1,1]\times[-1,1]. \]The unit circle occupies area
\[ \pi \]inside a square of area
\[ 4. \]Therefore, the probability that a random point lies in the circle is
\[ \frac{\pi}{4}. \]Estimating \(\pi\) from Samples
If \(N\) points are sampled and \(I\) land inside the unit circle, then
\[ \frac IN \]estimates
\[ \frac{\pi}{4}. \]Therefore,
\[ \boxed{\pi\approx4\frac IN}. \]More Samples Usually Improve Stability
A small sample can fluctuate substantially.
Larger numbers of independent samples generally produce more stable estimates.
But more samples also require more computation.
Randomization Does Not Mean Uncontrolled Behavior
A randomized algorithm is still mathematically specified.
It must define:
- what random choices are made;
- their probability distribution;
- how the random outcomes affect execution;
- what correctness or error guarantees follow.
Pseudorandomness in Computation
Real programs often use pseudorandom number generators.
These generate sequences that imitate randomness from an initial seed.
Using the same seed can reproduce the same sequence of random-looking choices.
Reproducibility
Reproducibility is important in testing randomized algorithms.
Fixing a random seed can allow the same randomized execution to be repeated exactly.
Different seeds can then be used to test robustness across many random paths.
Expected Running Time
Randomized algorithms are often analyzed using expected running time.
If possible running times are
\[ T_1,T_2,\ldots \]with probabilities
\[ p_1,p_2,\ldots, \]then the expected time is
\[ E[T]=\sum_i p_iT_i. \]Expected Time Is Not a Hard Maximum
An expected running time of
\[ O(n\log n) \]does not necessarily mean every execution finishes within a constant multiple of \(n\log n\).
It describes an average over the algorithm's random behavior.
Exact Randomized Algorithms
Randomized does not imply approximate.
A Las Vegas algorithm can use randomness internally while still guaranteeing an exact output.
Randomized quicksort, for example, still sorts the data exactly.
Approximate Randomized Algorithms
Some methods are both randomized and approximate.
They may return estimates whose error is bounded with high probability.
In such cases, we must describe both:
- solution quality;
- probability of meeting that quality guarantee.
Deterministic Approximation Algorithms
Approximation does not require randomness.
A deterministic approximation algorithm can always follow the same steps and still return a solution within a provable factor of the optimum.
Three Separate Questions
When classifying an algorithm, ask three different questions:
- Does it guarantee an exact or approximate answer?
- Is its control flow deterministic or randomized?
- What time and space resources does it require?
These properties should not be collapsed into one label.
Quality Versus Running Time
A practical algorithm may allow the user to trade solution quality for speed.
More computation may produce:
- a better approximation;
- a lower error probability;
- a more stable estimate;
- a more thorough search.
Anytime Algorithms
An anytime algorithm can return a usable solution before it has fully completed and can improve that solution if given more time.
This is useful when computation may be interrupted or when a fast initial answer is valuable.
Lower and Upper Bounds on Solution Quality
Optimization algorithms may maintain bounds on the unknown optimum.
For a minimization problem:
- a feasible solution gives an upper bound on \(OPT\);
- a proven lower estimate gives a lower bound on \(OPT\).
Narrowing the gap between these bounds gives information about solution quality.
Approximation Schemes
Some algorithm families allow a user-chosen accuracy parameter.
For example, a parameter
\[ \varepsilon>0 \]may control how close the result must be to optimal.
Smaller \(\varepsilon\) can mean higher accuracy but greater computational cost.
Accuracy Parameters Express Tradeoffs
A method may promise a solution within a factor such as
\[ 1+\varepsilon \]of optimal for a minimization problem.
The parameter allows a controlled tradeoff between approximation quality and running time.
Probability Parameters Express Confidence Tradeoffs
Randomized algorithms may also expose an error tolerance
\[ \delta. \]A statement such as
\[ \Pr(\text{failure})\le\delta \]makes the reliability guarantee explicit.
Smaller \(\delta\) usually requires more computation.
High Probability
In randomized algorithm analysis, a property may be said to hold with high probability when its failure probability becomes very small as the input grows.
The exact mathematical meaning depends on the stated bound and should be specified rather than assumed.
Randomized Verification
Sometimes it is easier to probabilistically check a claimed result than to recompute everything deterministically.
A randomized verifier may quickly detect incorrect answers with high probability.
Repetition can then reduce the chance that an incorrect answer escapes detection.
Decision Versus Optimization
Exact, approximate, and randomized methods can apply to different problem types.
A decision problem asks for a yes-or-no answer.
An optimization problem asks for the best feasible solution according to an objective.
Approximation language is especially common for optimization problems.
Feasibility Still Matters
An approximate optimization solution should still satisfy the problem's required constraints unless the method explicitly relaxes them.
Being near the optimal objective value does not excuse violating feasibility.
Randomized Algorithms Still Need Correctness Analysis
Randomized methods do not escape mathematical proof.
Their analysis may prove:
- correctness for every random outcome;
- an upper bound on error probability;
- an expected running-time bound;
- a high-probability performance guarantee.
Common Error: Calling Every Nonexact Method an Approximation Algorithm
A heuristic with no formal guarantee is not automatically an approximation algorithm in the technical sense.
Approximation algorithms come with provable quality bounds.
Common Error: Assuming Randomized Means Incorrect
Some randomized algorithms are always correct.
Randomness may affect only running time or internal choices.
Las Vegas algorithms are the standard example.
Common Error: Assuming Randomized Means Approximate
Randomness and approximation are separate dimensions.
A randomized sorting algorithm can still return the exact sorted order.
Common Error: Ignoring Error Probability
A Monte Carlo algorithm should not be described merely as "usually right."
The error probability should be bounded and stated mathematically whenever possible.
Common Error: Multiplying Probabilities Without Independence
The calculation
\[ p^k \]for \(k\) repeated failures assumes appropriate independence.
Without independence, this calculation may be invalid.
Common Error: Comparing Approximate Value with the Wrong Benchmark
Approximation quality should be measured relative to the true optimum or a mathematically justified bound on it.
Comparing only with another heuristic does not establish an approximation ratio.
Common Error: Confusing Expected Time with Worst-Case Time
Expected complexity averages over random behavior.
Worst-case complexity describes the most expensive valid execution.
They are different guarantees.
Common Error: Ignoring Reproducibility
Randomized implementations can be difficult to debug if random choices cannot be reproduced.
Recording or fixing seeds during testing can make failures repeatable.
A Reliable Procedure for Evaluating an Algorithmic Method
- State the problem and required output precisely.
- Determine whether an exact answer is required.
- Identify whether approximation is acceptable.
- If approximate, state the quality guarantee.
- Determine whether the algorithm is deterministic or randomized.
- If randomized, state what randomness affects: correctness, running time, or both.
- State any error probability or confidence guarantee.
- State time and space complexity.
- Check whether repetition can improve confidence or quality.
- Compare computational cost with the value of stronger guarantees.
Example: Exact Versus Approximate Optimization
Suppose an exact algorithm finds an optimum of
\[ OPT=100 \]but requires impractically large computation on big inputs.
A 1.1-approximation for the same minimization problem guarantees
\[ A\le1.1(100)=110. \]If it runs much faster, the tradeoff may be useful.
Example: Repeated Randomized Testing
Suppose one independent randomized test misses an error with probability
\[ \frac12. \]Repeating the test \(5\) independent times gives probability
\[ \left(\frac12\right)^5 = \boxed{\frac1{32}} \]that all five tests miss the error.
Example: Randomized Exact Sorting
Randomized quicksort may choose pivots randomly.
The random choices change the partition structure and running time.
But when the procedure finishes correctly, the output is still a fully sorted permutation of the input.
Thus it is randomized but exact.
Practice 1: Exactness
What defining guarantee does an exact algorithm provide?
Practice 2: Approximation Ratio
A 2-approximation for a minimization problem is applied to an instance whose optimum is \(50\).
What maximum cost does the approximation guarantee allow?
Practice 3: Heuristic or Approximation?
A method often produces good solutions quickly but has no proven bound on how close they are to optimal.
Is it more accurately described as a heuristic or an approximation algorithm?
Practice 4: Las Vegas
What does randomness affect in a Las Vegas algorithm?
Practice 5: Monte Carlo
What type of guarantee may a Monte Carlo algorithm sacrifice with small probability?
Practice 6: Repetition
A randomized algorithm has independent error probability
\[ \frac13 \]per run. If failure requires all four independent runs to fail, what is the resulting error probability?
Practice 7: Deterministic Versus Randomized
Can an algorithm be both randomized and exact?
Practice 8: Expected Time
Does an expected running-time bound necessarily give a hard upper bound on every possible run?
Practice 9: Monte Carlo Estimate
In the unit-circle estimate of \(\pi\), \(8000\) sampled points are used and \(6280\) fall inside the circle.
Estimate \(\pi\).
Practice 10: Algorithm Classification
An algorithm always returns a feasible solution within \(10\%\) of optimal, uses no random choices, and runs in polynomial time.
How should it be classified?
Practice Answers
Practice 1
An exact algorithm guarantees the correct or optimal answer required by the specification for every valid input.
Practice 2
A 2-approximation guarantees
\[ A\le2(50)=\boxed{100}. \]Practice 3
It is more accurately called a
\[ \boxed{\text{heuristic}}. \]No formal approximation guarantee was given.
Practice 4
Randomness affects the running time or execution path, while the returned answer remains correct.
Practice 5
A Monte Carlo algorithm may sacrifice
\[ \boxed{\text{correctness with a bounded small probability}}. \]Practice 6
\[ \left(\frac13\right)^4 = \boxed{\frac1{81}}. \]Practice 7
Yes. A Las Vegas algorithm is randomized but always correct.
Practice 8
No. Expected time is an average over random behavior and does not necessarily bound every individual execution.
Practice 9
\[ \pi\approx4\frac{6280}{8000} \] \[ =4(0.785) \] \[ =\boxed{3.14}. \]Practice 10
It is a
\[ \boxed{\text{deterministic approximation algorithm}}. \]It has a provable approximation guarantee and uses no randomness.
What to Remember
- Exact algorithms guarantee fully correct solutions but may be computationally expensive.
- Approximation algorithms trade optimality for efficiency while providing provable quality guarantees.
- Heuristics may work well without carrying formal approximation guarantees.
- Randomized algorithms use controlled random choices during execution.
- Las Vegas algorithms are always correct but have randomized running behavior.
- Monte Carlo algorithms may have a bounded probability of error.
- Independent repetition can reduce error probability.
- Expected complexity is different from worst-case complexity.
- Randomized algorithms can still be exact.
- Approximation and randomization are separate dimensions of algorithm design.
The most important habit is: state exactly what guarantee the algorithm provides—exactness, approximation quality, error probability, expected time, or some combination of these.
Completing Discrete Algorithms and Computation
The lessons in this section have developed a broad algorithmic toolkit: search, sorting, recursion, greedy methods, divide and conquer, dynamic programming, backtracking, graph algorithms, correctness, termination, and complexity analysis.
Exact, approximate, and randomized methods complete that toolkit by showing that algorithm design is not only about finding a procedure that works. It is also about choosing the right balance among certainty, speed, memory, scalability, and solution quality.