diff options
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 |