• — table of contents —
• Misc. background material
  • Probabilistic method
    • basic bounds
    • examples (Max Cut, Turán’s theorem)
    • method of conditional probabilities (Max Cut)
    • pessimistic estimators (Turáns theorem)
    • Chernoff bound
    • Chernoff bound proof
  • Bounds related to random stopping times
    • Wald’s equation
    • Wald’s equation for dependent increments
    • Markov bound for super-martingales
    • “Stopping-time” Chernoff bounds
    • Expected maximum (or minimum) of many sums
    • Expected deviation of a sum
  • Linear programming
    • modeling Set Cover and Multicommodity Flow
    • rounding an LP relaxation
  • Randomized rounding
  • Set Cover / greedy algorithm
  • Set Cover / Wolsey’s generalization
  • Lagrangian relaxation / example
  • Lagrangian relaxation / discussion
• Oblivious randomized rounding
  • Greedy examples
    • Greedy Set Cover I: unweighted ln(n)-approximation
    • Greedy Set Cover II: weighted H(n)-approximation via random stopping time
    • Greedy Set Cover III: weighted H(d)-approximation via localizing
    • Set Cover / alterations
    • Set Cover / using Markov to bound the cost
    • Set Cover / GRASP (greedy randomized search procedure; unweighted)
    • Maximum c-Matching / 2-approximation (local analysis; weighted)
    • Unconstrained Set Multicover
  • Lagrangian-relaxation examples
    • Multicommodity Flow I: Lagrangian relaxation via Chernoff
    • Multicommodity Flow II: width-independence via non-uniform increments
    • Multicommodity Flow III: better approximation via localization
    • Sparse strategies for zero-sum matrix games
    • Fractional Set Cover / unweighted
    • Fractional Set Cover
• Writing wordpress blog entries in laTeX with plog (plasTeX and blogpost)

Navigate using the menubar at the top of the window, and the arrows at the left and right edges.