CSCI4240
Advanced Algorithms: Randomization and Approximation
Concentration bounds, randomized rounding and linear-programming relaxations, random walks, local search, zero-sum games, streaming and hashing, and semidefinite programming.
Your progress
0/ 34 sections marked complete
Next section: Local search for maximum cut
Completion marks are saved in this browser.
This course in the web
In the CSCI4240 notes
- Theorem cards
- 74
- Definitions
- 52
- Counterexamples
- 36
- Concept lenses
- 17
- Histories of ideas
- 0
- Proof X-rays
- 40
No concept lens from this course is recorded in the web yet.
Counts cover the 34 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 74 · Definitions 52 · Counterexamples 36 · Concept lenses 17 · Proof X-rays 40
No concept lens from this course is recorded in the web yet.
Counts cover the 34 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 1 section
Local search
Approximation guarantees from local optimality.
Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Local search for maximum cut
Prove an approximation guarantee from a single-vertex local optimum.
Chapter 2 · 2 sections
Zero-sum games
Mixed strategies and optimality certificates.
Theorems 4 · Definitions 3Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Mixed strategies in finite zero-sum games
Use linear programming duality to explain optimal randomization in finite games.
- 2.2
No-regret play in multiplayer games
Use full-information multiplicative weights to construct approximate coarse correlated equilibria.
Chapter 3 · 4 sections
Concentration bounds
Multiplicative tail bounds for independent indicators.
Theorems 9Counterexamples 5Lenses 2Proof X-rays 6
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Chernoff bounds for independent indicators
Derive multiplicative tail bounds and apply them to sampling and sparse counts.
- 3.2
Concentration and independent repetition
Prove Markov and Chebyshev bounds and analyze amplification by independent trials.
- 3.3
Maximum load in balls and bins
Prove upper and lower bounds for the largest load using first and second moments.
- 3.4
Birthday collisions and second moments
Analyze collision probabilities and the independence assumptions behind them.
Chapter 4 · 5 sections
Randomized rounding
Randomized rounding and repair for set cover.
Theorems 12 · Definitions 8Counterexamples 5Lenses 4Proof X-rays 6
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Randomized rounding for set cover
Turn a fractional cover into a feasible cover and bound its expected cost.
- 4.2
Why linear-programming duality is exact
Prove strong duality by projecting inequalities and tracking nonnegative certificates.
- 4.3
Set cover: charging, linear relaxations, and primal–dual certificates
Prove harmonic greedy and frequency-based rounding guarantees, then build a feasible dual certificate while constructing a cover.
- 4.4
Metric traveling-salesperson approximation
Use spanning trees, Euler tours and metric shortcutting to bound tour cost.
- 4.5
A fully polynomial scheme for knapsack
Scale profits and solve a minimum-weight dynamic program with an explicit approximation guarantee.
Chapter 5 · 4 sections
Random walks
Amplification using spectral bounds.
Theorems 10 · Definitions 8Counterexamples 4Lenses 2Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Amplification by random walks
Bound repeated visits to a bad set using an absolute spectral bound.
- 5.2
Random walks and spectral mixing
Use eigenvalues of a regular graph to bound convergence of a random walk.
- 5.3
Random-walk search for 2-SAT
Use a distance potential to bound a randomized satisfying-assignment search.
- 5.4
Stationary distributions and lazy walks
Prove existence and a coupling-based convergence result for finite chains.
Chapter 6 · 7 sections
Conditional expectation
Derandomizing a Max-2SAT guarantee.
Theorems 14 · Definitions 11Counterexamples 7Lenses 4Proof X-rays 7
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Max-2SAT and conditional expectation
Turn the expected value of a random assignment into a deterministic guarantee.
- 6.2
Random contraction for minimum cuts
Prove the success probability of a random contraction algorithm and amplify it by repetition.
- 6.3
Polynomial identity testing by random evaluation
Prove the Schwartz–Zippel bound and apply it to bipartite perfect matching.
- 6.4
Randomized verification of matrix products
Use random vectors to verify a matrix product with one-sided error.
- 6.5
The Lovász local lemma
Prove the local lemma and use sparse dependencies to show that bad events can all be avoided.
- 6.6
Random cuts and conditional expectation
Use a random partition to prove a cut exists and derandomize it by conditional expectations.
- 6.7
Random assignment and MAX-SAT approximation
Analyze weighted clause satisfaction and derandomize by conditional expectation.
Chapter 7 · 6 sections
Online decisions
Competitive analysis of ski rental.
Theorems 14 · Definitions 17Counterexamples 7Proof X-rays 7
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Online decisions and the ski-rental problem
Prove a deterministic competitive guarantee and matching lower bound.
- 7.2
Continuous ski rental and randomized thresholds
Contrast the discrete model with continuous-time competitive ratios and worked solutions.
- 7.3
Online paging and competitive analysis
Analyze marking phases and adversarial requests in the paging problem.
- 7.4
The sharp competitive bound for LRU paging
Use a recency-weighted potential to prove that least recently used paging is k-competitive.
- 7.5
Randomized marking for online paging
Bound expected paging cost against an oblivious adversary using harmonic sums.
- 7.6
List scheduling on identical machines
Prove a tight makespan guarantee using load and longest-job lower bounds.
Chapter 8 · 1 section
Randomized coverage
Expected waiting times and high-probability coverage.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Collecting all coupons
Analyze a randomized stopping time and a coverage tail bound.
Chapter 9 · 1 section
Sampling streams
Uniform reservoir sampling and finite-population estimation.
Theorems 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Reservoir sampling and estimating a stream fraction
Prove a uniform sample invariant for an unknown-length stream and derive a finite-population error bound.
Chapter 10 · 2 sections
Hashing and sketches
Hashing and sketches
Theorems 4Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Pairwise-independent binary hashing
Construct an affine hash family and analyze collision-based guarantees.
- 10.2
Count–Min sketches for frequency estimation
Bound collision error with pairwise-independent hashing and independent repetitions.
Chapter 11 · 1 section
Semidefinite programming
Semidefinite programming
Theorems 2 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Max-Cut vectors and random hyperplanes
Derive a semidefinite relaxation, prove the angle crossing probability, and obtain an exact expected approximation constant.