Randomized and Approximation Algorithms
Randomized and approximation algorithms trade exactness or determinism for efficiency: randomized algorithms use random choices to gain speed or simplicity, while approximation algorithms find provably near-optimal solutions to problems too hard to solve exactly.
Definition
Randomized algorithms make random choices during execution and are analyzed for expected running time or probability of correctness; approximation algorithms run efficiently and return solutions guaranteed to be within a proven factor of optimal for hard optimization problems.
Scope
This area covers algorithms that relax the goal of an exact, deterministic answer. It includes randomized algorithms (Las Vegas and Monte Carlo), with their probabilistic guarantees; approximation algorithms for NP-hard optimization with proven approximation ratios; and online algorithms that must decide without knowing the future, analyzed by competitive ratio. These are the standard responses to intractability and to settings with uncertainty, building on complexity analysis and design paradigms.
Sub-topics
Core questions
- How does randomization improve running time, simplicity, or robustness?
- What is the difference between Las Vegas and Monte Carlo guarantees?
- How is the quality of an approximation algorithm quantified by an approximation ratio?
- Which NP-hard problems admit good approximations, and which resist them?
- How are online decisions, made without future information, evaluated competitively?
Key concepts
- randomized algorithms
- Las Vegas and Monte Carlo
- expected running time
- concentration inequalities
- approximation ratio
- polynomial-time approximation scheme
- online algorithms
- competitive ratio
Key theories
- Randomization for efficiency
- Random choices can yield algorithms that are faster or simpler than the best deterministic ones, with guarantees on expected time (Las Vegas) or on error probability (Monte Carlo), often using concentration inequalities for analysis.
- Approximation ratios for NP-hard problems
- When exact solutions are intractable, an approximation algorithm provides a solution provably within a factor (the approximation ratio) of the optimum; the achievable ratio characterizes how well a problem can be approximated.
Clinical relevance
These methods are the practical toolkit for hard and uncertain problems: randomized algorithms drive primality testing in cryptography, hashing, and load balancing; approximation algorithms produce usable solutions for NP-hard scheduling, routing, clustering and facility-location problems; and online algorithms model caching, paging, and resource allocation where decisions must be made in real time.
History
Randomized algorithms gained prominence with the Solovay-Strassen and Rabin primality tests of the 1970s and Rabin's broader advocacy of probabilistic methods. Approximation algorithms grew alongside NP-completeness theory from the 1970s, and competitive analysis of online algorithms was formalized by Sleator and Tarjan in the 1980s, together forming the modern study of inexact and probabilistic algorithms.
Key figures
- Rajeev Motwani
- Prabhakar Raghavan
- Vijay Vazirani
- Michael Rabin
- Robert Solovay
- Volker Strassen
Related topics
Seminal works
- motwani1995
- vazirani2001
- cormen2009
Frequently asked questions
- Are randomized algorithms unreliable because they use randomness?
- No. Las Vegas algorithms always return a correct answer and only their running time varies. Monte Carlo algorithms may err, but the error probability can be driven arbitrarily low by repetition. Their guarantees are precise probabilistic statements, not unpredictability.
- Why use an approximation algorithm instead of just finding the optimal solution?
- For NP-hard optimization problems, finding the exact optimum can be infeasible for large inputs. An approximation algorithm runs in polynomial time and guarantees a solution within a known factor of optimal, which is often good enough and far more practical than waiting for an exact answer.