diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2013-07-02 16:01:49 +0200 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2013-07-02 16:01:49 +0200 |
| commit | 1bd9da9fc37dc4f659a261ff65914feef1ef64f0 (patch) | |
| tree | 1d74e72e52fdd708a77e75c8abf1240b7dbd722d /approximation.tex | |
| parent | c569d13f707706c49aea4cdd3635a0f73ed38f86 (diff) | |
| download | recommendation-1bd9da9fc37dc4f659a261ff65914feef1ef64f0.tar.gz | |
Rewrite the hand-wavy induction
Diffstat (limited to 'approximation.tex')
| -rw-r--r-- | approximation.tex | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/approximation.tex b/approximation.tex index 81a6d0c..23dc212 100644 --- a/approximation.tex +++ b/approximation.tex @@ -23,7 +23,7 @@ problem with a constant approximation ratio to \EDP{} (Proposition~\ref{prop:relaxation}) and then showing how to approximately solve this problem in a monotone way. -\subsection{A concave relaxation of \EDP}\label{sec:concave} +\subsection{A Concave Relaxation of \EDP}\label{sec:concave} A classical way of relaxing combinatorial optimization problems is \emph{relaxing by expectation}, using the so-called \emph{multi-linear} @@ -87,7 +87,7 @@ proposition which is also proved in the Appendix. $L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$. \end{proposition} -\subsection{Solving a convex problem monotonously}\label{sec:monotonicity} +\subsection{Solving a Convex Problem Monotonously}\label{sec:monotonicity} Note, that the feasible set in Problem~\eqref{eq:primal} increases (for the inclusion) when the cost decreases. As a consequence, $c\mapsto L^*_c$ is |