diff options
| -rwxr-xr-x | approximation.tex | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/approximation.tex b/approximation.tex index 546961f..901e1dd 100755 --- a/approximation.tex +++ b/approximation.tex @@ -34,7 +34,7 @@ In the first part of this section, we address this issue by designing a convex r A classical way of relaxing combinatorial optimization problems is \emph{relaxing by expectation}, using the so-called \emph{multi-linear} extension of the objective function $V$ (see, \emph{e.g.}, \cite{calinescu2007maximizing,vondrak2008optimal,dughmi2011convex}). -This is because this extension can yield approximation guarantees for a wide class of combinatorial problems through \emph{pipage rounding}, a technique proposed by \citeN{pipage}. Crucially for our purposes, such relaxations in general preserve monotonicity which, as discussed, is required in mechanism design. +This is because this extension can yield approximation guarantees for a wide class of combinatorial problems through \emph{pipage rounding}, a technique proposed by \citeN{pipage}. In general, such relaxations preserve monotonicity which, as discussed, is required in mechanism design. Formally, let $P_\mathcal{N}^\lambda$ be a probability distribution over $\mathcal{N}$ parametrized by $\lambda\in [0,1]^n$, where a set $S\subseteq \mathcal{N}$ sampled from $P_\mathcal{N}^\lambda$ is constructed as follows: each $i\in \mathcal{N}$ is selected to be in $S$ independently with probability $\lambda_i$, \emph{i.e.}, %\begin{displaymath} |