Notes on algorithms

Lecture notes on algorithms

Menu

Skip to content

–

This entry was posted in Uncategorized on December 9, 2013 by Neal.

Post navigation

CONTENTS: (show all|collapse)

— table of contents — Misc. background material

Probabilistic method
Bounds related to random stopping times
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
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)

Search for:

Misc. background material

Copyright © 2026 by Neal Young . All Rights Reserved.