diff options
| -rwxr-xr-x | appendix.tex | 2 | ||||
| -rwxr-xr-x | approximation.tex | 4 | ||||
| -rwxr-xr-x | main.tex | 2 | ||||
| -rwxr-xr-x | notes.bib | 4 | ||||
| -rwxr-xr-x | paper.tex | 2 |
5 files changed, 5 insertions, 9 deletions
diff --git a/appendix.tex b/appendix.tex index 1a5bcc5..6926e00 100755 --- a/appendix.tex +++ b/appendix.tex @@ -880,7 +880,7 @@ Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2} gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed -Finally, we prove the lower bound stated in Theorem~\ref{thm:main} +Finally, we prove the lower bound stated in Theorem~\ref{thm:main}. Suppose, for contradiction, that such a mechanism exists. From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must diff --git a/approximation.tex b/approximation.tex index 901e1dd..dc39e5b 100755 --- a/approximation.tex +++ b/approximation.tex @@ -127,8 +127,8 @@ In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\del \begin{proposition}\label{prop:monotonicity} For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, - there exists an algorithm computes a $\delta$-decreasing, + there exists an algorithm which computes a $\delta$-decreasing, $\varepsilon$-accurate approximation of $L^*_c$. The running time of the algorithm is $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$. \end{proposition} -The proof and the algorithm (Algorithm~\ref{alg:monotone}) are in Appendix~\ref{proofofproprelaxation}. +The proof and the algorithm (Algorithm~\ref{alg:monotone}) are in Appendix~\ref{proofofpropmonotonicity}. @@ -20,7 +20,7 @@ The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimi Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} -The detailed description of our proposed mechanism (see Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}. +The detailed description of our proposed mechanism (Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}. @@ -104,10 +104,8 @@ year = 2012 @incollection{calinescu2007maximizing, title={Maximizing a submodular set function subject to a matroid constraint}, author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan}, - booktitle={Integer programming and combinatorial optimization}, - pages={182--196}, + booktitle={IPCO}, year={2007}, - publisher={Springer} } @@ -38,10 +38,8 @@ \input{main} \section{Conclusions}\label{sec:concl} \input{conclusion} -\begin{comment} \section*{Acknowledgments} \input{ack} -\end{comment} \bibliographystyle{splncsnat} \begin{footnotesize} \bibliography{notes} |