diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 29 |
1 files changed, 17 insertions, 12 deletions
@@ -2,7 +2,7 @@ In this section we present our mechanism for \SEDP. Prior approaches to budget feasible mechanisms for sudmodular maximization build upon the full information -case which we discuss first. +case, which we discuss first. \subsection{Submodular Maximization in the Full Information Case} @@ -16,8 +16,8 @@ element $i$ to be included is the one which maximizes the i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy} \end{align} This is repeated until the sum of costs of elements in $S$ reaches the budget -constraint $B$. Denote by $S_G$ the set constructed by this heuristic and by -$i^* = \argmax_{i\in\mathcal{N}} V(\{i\})$, then the following lemma holds: +constraint $B$. Denote by $S_G$ the set constructed by this heuristic and let +$i^*$ be the element of maximum value. Then, the following lemma holds: \begin{lemma}~\cite{chen}\label{lemma:greedy-bound} Let $S_G$ be the set computed by the greedy algorithm and let $i^* = \argmax_{i\in\mathcal{N}} V(\{i\}).$ We have: @@ -25,6 +25,7 @@ $i^* = \argmax_{i\in\mathcal{N}} V(\{i\}).$ We have: OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). \end{displaymath} \end{lemma} + This lemma immediately implies that the following algorithm: \begin{equation}\label{eq:max-algorithm} \textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\} @@ -45,10 +46,10 @@ full-information case after removing $i^*$ from the set $\mathcal{N}$: OPT_{-i^*} \defeq \max_{S\subseteq\mathcal{N}\setminus\{i^*\}} \Big\{V(S) \;\Big| \; \sum_{i\in S}c_i\leq B\Big\} \end{equation} -\citeN{singer-mechanisms} and \citeN{chen} prove that using the following +\citeN{singer-mechanisms} and \citeN{chen} prove that the following allocation: \begin{displaymath} -\textbf{if}\; V(\{i^*\}) \geq C. OPT_{-i^*}\; \textbf{return}\; \{i^*\} +\textbf{if}\; V(\{i^*\}) \geq C \cdot OPT_{-i^*}\; \textbf{return}\; \{i^*\} \;\textbf{else return}\; S_G \end{displaymath} yields a 8.34-approximation mechanism for an appropriate $C$ (see also @@ -79,9 +80,9 @@ denotes the indicator vector of $S$. The optimization program \leq B\right\}\label{relax} \end{align} -One of the main technical contribution of \citeN{chen} and -\citeN{singer-influence} is to come up with appropriate relaxations for -\textsc{Knapsack} and \textsc{Coverage} respectively. +One of the main technical contributions of \citeN{chen} and +\citeN{singer-influence} is to come up with appropriate such relaxations for +\textsc{Knapsack} and \textsc{Coverage}, respectively. \subsection{Our Approach} @@ -98,7 +99,8 @@ method for self-concordant functions in \cite{boyd2004convex}, shows that finding the maximum of $L$ to any precision $\varepsilon$ can be done in $O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization problem, $L^*$ satisfies the required monotonicity property. The main challenge -will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to $OPT$. +will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to +$OPT_{-i^*}$. \begin{algorithm}[t] \caption{Mechanism for \SEDP{}}\label{mechanism} @@ -138,9 +140,10 @@ be found in~\cite{singer-mechanisms}. We can now state our main result: \begin{theorem}\label{thm:main} \sloppy - The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individually rational - and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism - runs in time $O\left(\text{poly}(n, d, + The allocation described in Algorithm~\ref{mechanism}, along with threshold + payments, is truthful, individually rational and budget feasible. + Furthermore, there exists an absolute constant $C$ such that, for any + $\varepsilon>0$, the mechanism runs in time $O\left(\text{poly}(n, d, \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that: \begin{align*} OPT @@ -148,6 +151,8 @@ We can now state our main result: \varepsilon\\ & \simeq 12.98V(S^*) + \varepsilon \end{align*} + The value of the constant $C$ is given by \eqref{eq:constant} in + Section~\ref{sec:proofofmainthm}. \end{theorem} \fussy |