linear constraints

3 files changed, 5 insertions, 5 deletions

diff --git a/approximation.tex b/approximation.tex
index c306a75..aed79a0 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -112,7 +112,7 @@ The proof of this proposition can be found in Appendix~\ref{proofofproprelaxatio
  The $\log\det$ objective function of \eqref{eq:primal} is strictly concave and \emph{self-concordant} \cite{boyd2004convex}. The maximization of a concave, self-concordant function subject to a set of linear constraints can be performed through the \emph{barrier method} (see, \emph{e.g.}, \cite{boyd2004convex} Section 11.5.5 for  general self-concordant optimization as well as \cite{vandenberghe1998determinant} for a detailed treatment of the $\log\det$ objective). The performance of the barrier method is summarized in our case by the following lemma:
 \begin{lemma}[\citeN{boyd2004convex}]\label{lemma:barrier}
 For any $\varepsilon>0$, the barrier method computes  an 
-approximation $\hat{L}^*_c$ that is $\varepsilon$-accurate, \emph{i.e.}, it satisfies $|\hat L^*_c- L^*_c|\leq \varepsilon$, in time $O\left(poly(n,d,\log\log\varepsilon^{-1})\right)$.
+approximation $\hat{L}^*_c$ that is $\varepsilon$-accurate, \emph{i.e.}, it satisfies $|\hat L^*_c- L^*_c|\leq \varepsilon$, in time $O\left(poly(n,d,\log\log\varepsilon^{-1})\right)$. The same guarantees apply for maximizing $L$ subject to an arbitrary set of $O(n)$ linear constraints.
 \end{lemma}
 
  Clearly, the optimal value $L^*_c$ of \eqref{eq:primal} is monotone in $c$. Formally, for any two $c,c'\in \reals_+^n$ s.t.~$c\leq c'$ coordinate-wise, $\dom_{c'}\subseteq \dom_c$ and thus $L^*_c\geq L^*_{c'}$. Hence, the map $c\mapsto L^*_c$ is non-increasing. Unfortunately, the same is not true for the output $\hat{L}_c^*$ of the barrier method: there is no guarantee that the $\epsilon$-accurate approximation $\hat{L}^*_c$ exhibits any kind of monotonicity.
diff --git a/intro.tex b/intro.tex
index 3a2925b..4d8b5dd 100644
--- a/intro.tex
+++ b/intro.tex
@@ -64,7 +64,7 @@ We note that the objective \eqref{obj} is submodular. Using this fact, applying
 From a technical perspective, we propose a convex optimization problem and establish that its optimal value within a constant factor from the optimal value of \EDP.  
  In particular, we show our relaxed objective is within a constant factor from the so-called multi-linear extension of  \eqref{obj}, which in turn can be related to \eqref{obj} through pipage rounding. We establish the constant factor to the multi-linear extension by bounding  the partial derivatives of these two functions; we achieve the latter by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
 
-Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not nevessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; in turn, we also show that this algorithm can be employed to design a $\delta$-truthful mechanism for \EDP{}.
+Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not necessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; in turn, we also show that this algorithm can be employed to design a $\delta$-truthful mechanism for \EDP{}.
 
 
 %This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.   %{\bf FIX the last sentence}
diff --git a/notes.bib b/notes.bib
index c94f9c5..2a6357a 100644
--- a/notes.bib
+++ b/notes.bib
@@ -52,14 +52,14 @@ year = 2012
 
 
 
-@article{approximatemechanismdesign,
+@inproceedings{approximatemechanismdesign,
   author    = {Kobbi Nissim and
                Rann Smorodinsky and
                Moshe Tennenholtz},
   title     = {Approximately Optimal Mechanism Design via Differential
                Privacy},
-  year      = {2010},
-  ee        = {http://arxiv.org/abs/1004.2888},
+  year      = {2012},
+  booktitle        = {Innovations in Theoretical Computer Science (ITCS)}
 }
 
 @inproceedings{mcsherrytalwar,