From 1bd9da9fc37dc4f659a261ff65914feef1ef64f0 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Tue, 2 Jul 2013 16:01:49 +0200 Subject: Rewrite the hand-wavy induction --- approximation.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'approximation.tex') 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 -- cgit v1.2.3-70-g09d2