diff options
| -rw-r--r-- | paper.tex | 20 |
1 files changed, 17 insertions, 3 deletions
@@ -229,6 +229,16 @@ problem. Explain the goals: \section{Main result} +Explain: +\begin{itemize} + \item the mechanism uses the greedy heuristic + \item we know that the maximum of greedy and meatiest guy is a good + approximation, but not incentive compatible + \item instead compare the value of the meatiest guy to $L(x^*)$ (introduce + $L(x^*)$ which can be easily computed and is not too far from the greedy + value +\end{itemize} + \begin{algorithm}\label{mechanism} \caption{Mechanism for ridge regression} \begin{algorithmic}[1] @@ -251,11 +261,15 @@ problem. Explain the goals: \end{algorithmic} \end{algorithm} -Choosing $C=...$ we have: - \begin{theorem} The mechanism is truthful, individually rational, budget feasible. - Furthermore, by choosing $C= ...$ we get an approximation ratio of: + Furthermore, choosing: + \begin{multline*} + C = C^* = \frac{5e-1 + C_\mu(2e+1)}{2C_\mu(e-1)}\\ + + \frac{\sqrt{C_\mu^2(1+2e)^2 + + 2C_\mu(14e^2+5e+1) + (1-5e)^2}}{2C_\mu(e-1)} + \end{multline*} + we get an approximation ratio of: \begin{multline*} 1 + C^* = \frac{5e-1 + C_\mu(4e-1)}{2C_\mu(e-1)}\\ + \frac{\sqrt{C_\mu^2(1+2e)^2 |