diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 49 |
1 files changed, 24 insertions, 25 deletions
@@ -92,7 +92,7 @@ $\id_S$ denotes the indicator vector of $S$. The optimization program \leq B\right\}\label{relax} \end{align} Substituting $OPT'_{-i^*}$ for $OPT_{-i^*}$ like before works for specific problems like \textsc{Knapsack}~\cite{chen} and -\textsc{Coverage}~\cite{singer-influence}. For other instances of sub modular function, this overall technology +\textsc{Coverage}~\cite{singer-influence}. For other instances of submodular function, this overall technology has to be applied and extended. \end{itemize} @@ -257,9 +257,9 @@ We can now state our main result: \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that: \begin{align*} OPT - & \leq \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)} V(S^*)+ + & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+ \varepsilon\\ - & \simeq 19.68V(S^*) + \varepsilon + & \simeq 12.98V(S^*) + \varepsilon \end{align*} \end{theorem} @@ -296,7 +296,7 @@ contribution; the proof of this lemma can be found in Section~\ref{sec:relaxatio $O(\text{poly}(n, d))$ and the mechanism only involves a linear number of queries to the function $V$. The function $\log\det$ is concave and self-concordant (see - \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find + \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$ of iterations of Newton's method. Each iteration can be done in time $O(\text{poly}(n, d))$. Thus, line 3 of Algorithm~\ref{mechanism} can be computed in time @@ -315,7 +315,7 @@ following lemma which establishes that $OPT'$, the optimal value \eqref{relax} is not too far from $OPT$. \begin{lemma}\label{lemma:relaxation} %\begin{displaymath} - $ OPT' \leq 4 OPT + $ OPT' \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$ %\end{displaymath} \end{lemma} @@ -331,7 +331,7 @@ Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm $\varepsilon$, then the set $S^*$ allocated by the mechanism is such that: \begin{align} OPT - \leq \frac{14e\!-\!3 + \sqrt{160e^2\!-\!48e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound} + \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound} \end{align} %\end{lemma} To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume that on line 3 of algorithm~\ref{mechanism}, a quantity @@ -355,39 +355,39 @@ Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm from Lemmas \ref{lemma:relaxation} and \ref{lemma:greedy-bound}: \begin{align*} V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}'+ \frac{\varepsilon}{C}\leq \frac{1}{C} - \big(4 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\ - & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G) + \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\ + & \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G) + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C} \end{align*} - Thus, if $C$ is such that $C(e-1) -10e +2 > 0$, + Thus, if $C$ is such that $C(e-1) -6e +2 > 0$, \begin{align*} - V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G) - + \frac{(e-1)\varepsilon}{C(e-1)- 10e + 2} + V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) + + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2} \end{align*} Finally, using again Lemma~\ref{lemma:greedy-bound}, we get: \begin{multline}\label{eq:bound2} - OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C - (e-1) -10e +2}\right) V(S_G)\\ - +\frac{2e\varepsilon}{C(e-1)- 10e + 2} + OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{4e}{C + (e-1) -6e +2}\right) V(S_G)\\ + +\frac{2e\varepsilon}{C(e-1)- 6e + 2} \end{multline} To minimize the coefficients of $V_{i^*}$ and $V(S_G)$ in \eqref{eq:bound1} and \eqref{eq:bound2} respectively, we wish to chose for $C=C^*$ such that: \begin{displaymath} C^* = \argmin_C - \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C (e-1) -10e +2} + \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2} \right)\right) \end{displaymath} - This equation has two solutions. Only one of those is such that: - $ C(e-1) -10e +2 \geq 0$. + This equation has two solutions. Only one of those is such that + $C(e-1) -6e +2 \geq 0$. %which is needed in the above derivation. This solution is: \begin{align} - C^* = \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} \label{eq:c} + C^* = \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c} \end{align} For this solution, % \begin{displaymath} - $ \frac{2e\varepsilon}{C^*(e-1)- 10e + 2}\leq \varepsilon. $ + $ \frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon. $ % \end{displaymath} 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 @@ -436,7 +436,7 @@ if we define: - e_j)\big) \end{displaymath} where $e_i$ and $e_j$ are two vectors of the standard basis of -$\reals^{n}$, then $\tilde{F}$ is convex. Hence its maximum over the interval: +$\reals^{n}$, then $\tilde{F}_\lambda$ is convex. Hence its maximum over the interval: \begin{displaymath} I_\lambda = \Big[\max(-\lambda_i,\lambda_j-1), \min(1-\lambda_i, \lambda_j)\Big] \end{displaymath} @@ -444,7 +444,7 @@ is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th or the $j$-th component of $\lambda$ becomes integral. The lemma below proves that we can similarly trade a fractional component for -an other until one of them becomes integral \emph{while maintaining the +another until one of them becomes integral \emph{while maintaining the feasibility of the point at which $F$ is evaluated}. Here, by feasibility of a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_i c_i \leq B$. \begin{lemma}[Rounding]\label{lemma:rounding} @@ -697,14 +697,13 @@ Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) \end{equation} Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$ denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$. - Using the fact that $F$ is linear with respect to the $i$-th - component and is a relaxation of the value function, we get: + By definition of the multi-linear extension $F$: \begin{displaymath} - F(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\}) + F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\}) \end{displaymath} Using the submodularity of $V$: \begin{displaymath} - F(\bar{\lambda}) \leq 2 V(S) + V(i) + F(\bar{\lambda}) \leq V(S) + V(i) \end{displaymath} Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and $V(S)\leq OPT$. Hence: |