From 560eb3da4a23ed3317f8678688f2a55fc7d3c1bf Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 22 Sep 2013 23:22:03 +0200 Subject: done --- approximation.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) 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} -- cgit v1.2.3-70-g09d2