summaryrefslogtreecommitdiffstats
path: root/approximation.tex
diff options
context:
space:
mode:
authorStratis Ioannidis <stratis@Stratiss-MacBook-Air.local>2013-09-22 23:22:03 +0200
committerStratis Ioannidis <stratis@Stratiss-MacBook-Air.local>2013-09-22 23:22:03 +0200
commit560eb3da4a23ed3317f8678688f2a55fc7d3c1bf (patch)
tree48d429d7729a1dbda8202aeb99c41e71552397bc /approximation.tex
parent1729c3e637ff54707bcfc3e386237fe425f4988c (diff)
downloadrecommendation-560eb3da4a23ed3317f8678688f2a55fc7d3c1bf.tar.gz
done
Diffstat (limited to 'approximation.tex')
-rwxr-xr-xapproximation.tex2
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}