Topics

Introduction

Max-3SAT and a tight 7/8-approximation

MST-based Algorithms

The Traveling Salesman Problem (TSP)

The Steiner Tree Problem,
    Approximation Factor Preserving Reductions

(Supplement) Minimum Cycle Cover and a 4-approximation

Vertex Cover & Set Cover

The Vertex Cover Problem and 2-approximation algorithms
    The Set Cover Problem and an (Hn)-approximation

Parametric Search via Approximate-or-Refute

The k-Center Problem and 2-approximation

Approximate to any Desirable Degree

FPTAS for the Knapsack Problem,
    Existence of FPTAS

Linear Programming-based Methods and LP Duality

The basic framework & simple rounding scheme,
    The Weak Duality Theorem

2-approximations for Vertex Cover via LP-rounding and Dual-Fitting

Extreme Point Structure of Linear Polytopes

Half-integrality of vertex cover,
Unrelated machine scheduling and a 2-approximation

Semidefinite Programming (SDP)

The max-cut problem and a 0.878-approximation