\documentclass[12pt]{article} \usepackage{wide,amsmath} $$\newcommand{\indx}{{\it index}}$$ $$\newcommand\xhat{{\hat x}}$$ $$\newcommand\what{{\hat w}}$$ $$\newcommand\zhat{{\hat z}}$$ $$\newcommand\Phat{{\hat P}}$$ \parindent0pt

Approximation Algorithms

NP-completeness.

Recall definition of approximation algorithms.

The Probabilistic Method---Value of Random Answers

Idea: to show an object with certain properties exists

Max-Cut:

Set balancing.

MAX SAT

Sometimes, it's hard to get hands on a good probability distribution of random answers.

Define.

random set

LP $$ \begin{eqnarray*} \max &&\sum z_j\\ \sum_{i \in C_j^+} y_i + \sum_{i \in C_j^-} (1-y_1) &\ge &z_j \end{eqnarray*} $$

Analysis

LP good for small clauses, random for large.

Set Cover

Wiring

Problem formulation

Linear Programs, integer linear programs

IP formulation Rounding Generalize