 Lecture notes on randomized approximation algorithms

Unsigned lecture notes in CS 4820: Algorithms, Spring 2011. The masthead identifies Cornell University and dates the document 2 May 2011. No individual author or course instructor is established. Cornell University is the institutional issuer and web host.

Online text: www.cs.cornell.edu/courses/cs4820/2011sp/handouts/approx_algs.pdf

Cited passages: Printed p. 1, heading and §1.1: institutional issuer, course, explicit date, independent random vertex placement and half-total-weight expectation.; §1.1.2, printed pp. 2–3: partial-assignment expectation, Algorithms 1–2, nondecreasing expectation, half-total-edge-weight guarantee and linear-time adjacency-list implementation..