Skip to content

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.

11 chapters · 34 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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 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

  1. 2.1

    Mixed strategies in finite zero-sum games

    Use linear programming duality to explain optimal randomization in finite games.

  2. 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

  1. 3.1

    Chernoff bounds for independent indicators

    Derive multiplicative tail bounds and apply them to sampling and sparse counts.

  2. 3.2

    Concentration and independent repetition

    Prove Markov and Chebyshev bounds and analyze amplification by independent trials.

  3. 3.3

    Maximum load in balls and bins

    Prove upper and lower bounds for the largest load using first and second moments.

  4. 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

  1. 4.1

    Randomized rounding for set cover

    Turn a fractional cover into a feasible cover and bound its expected cost.

  2. 4.2

    Why linear-programming duality is exact

    Prove strong duality by projecting inequalities and tracking nonnegative certificates.

  3. 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.4

    Metric traveling-salesperson approximation

    Use spanning trees, Euler tours and metric shortcutting to bound tour cost.

  5. 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

  1. 5.1

    Amplification by random walks

    Bound repeated visits to a bad set using an absolute spectral bound.

  2. 5.2

    Random walks and spectral mixing

    Use eigenvalues of a regular graph to bound convergence of a random walk.

  3. 5.3

    Random-walk search for 2-SAT

    Use a distance potential to bound a randomized satisfying-assignment search.

  4. 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

  1. 6.1

    Max-2SAT and conditional expectation

    Turn the expected value of a random assignment into a deterministic guarantee.

  2. 6.2

    Random contraction for minimum cuts

    Prove the success probability of a random contraction algorithm and amplify it by repetition.

  3. 6.3

    Polynomial identity testing by random evaluation

    Prove the Schwartz–Zippel bound and apply it to bipartite perfect matching.

  4. 6.4

    Randomized verification of matrix products

    Use random vectors to verify a matrix product with one-sided error.

  5. 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.6

    Random cuts and conditional expectation

    Use a random partition to prove a cut exists and derandomize it by conditional expectations.

  7. 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

  1. 7.1

    Online decisions and the ski-rental problem

    Prove a deterministic competitive guarantee and matching lower bound.

  2. 7.2

    Continuous ski rental and randomized thresholds

    Contrast the discrete model with continuous-time competitive ratios and worked solutions.

  3. 7.3

    Online paging and competitive analysis

    Analyze marking phases and adversarial requests in the paging problem.

  4. 7.4

    The sharp competitive bound for LRU paging

    Use a recency-weighted potential to prove that least recently used paging is k-competitive.

  5. 7.5

    Randomized marking for online paging

    Bound expected paging cost against an oblivious adversary using harmonic sums.

  6. 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

  1. 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

  1. 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

  1. 10.1

    Pairwise-independent binary hashing

    Construct an affine hash family and analyze collision-based guarantees.

  2. 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

  1. 11.1

    Max-Cut vectors and random hyperplanes

    Derive a semidefinite relaxation, prove the angle crossing probability, and obtain an exact expected approximation constant.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details