diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 20 |
1 files changed, 12 insertions, 8 deletions
@@ -19,8 +19,12 @@ included in $S$ is the one with the highest \emph{marginal-value-per-cost}: \end{align} This process terminates when no more items can be added to $S$ using \eqref{greedy} under budget $B$. This is the generalization of the \emph{value-per-cost} ratio used in the greedy approximation algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular -functions, the marginal value of an element in \eqref{greedy} depends on the set to which it the element is added. -% +functions, the marginal value of an element in \eqref{greedy} depends on the set to which the element is added. +Similarly, the value of an element depends on the set in which it is +considered. However, in the following, the value of an element $i$ will refer to +its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write +$V(i)$ instead of $V(\{i\})$. + Unfortunately, even for the full information case, the greedy algorithm gives an unbounded approximation ratio. Let $i^* = \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value. @@ -28,7 +32,7 @@ unbounded approximation ratio. Let $i^* %It has been noted by Khuller \emph{et al.}~\cite{khuller} that For the maximum coverage problem, taking the maximum between the greedy solution and $V(i^*$) -gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller} . In the general case, +gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general case, \junk{we have the following result from Singer \cite{singer-influence} which follows from Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...} @@ -83,10 +87,10 @@ problems, Chen et al.~\cite{chen} %for \textsc{Knapsack} and Singer propose comparing $V(i^*)$ to %$OPT(R_{\mathcal{N}\setminus\{i\}}, B)$, where $R$ denotes the optimal value of a \emph{fractional relaxation} of the function $V$ over the set -$\mathcal{N}$. A fuction $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube $[0, 1]^{n}$ is a fractional relaxation of $V$ +$\mathcal{N}$. A function $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube $[0, 1]^{n}$ is a fractional relaxation of $V$ over the set $\mathcal{N}$ if %(a) $R$ is a function defined on the hypercube $[0, 1]^{n}$ and (b) - $R(\mathbf{1}_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where -$\mathbf{1}_S$ denotes the indicator vector of $S$. The optimization program + $R(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where +$\id_S$ denotes the indicator vector of $S$. The optimization program \eqref{eq:non-strategic} extends naturally to such relaxations: \begin{align} OPT' = \argmax_{\lambda\in[0, 1]^{n}} @@ -180,7 +184,7 @@ characterization from Singer \cite{singer-mechanisms} gives a formula to We can now state our main result: \begin{theorem}\label{thm:main} - The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individiually rational + 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 has complexity $O\left(\text{poly}(n, d, \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that: @@ -195,7 +199,7 @@ We can now state our main result: Note that this implies we construct a poly-time mechanism with accuracy arbitrarily close to 19.68, by taking $\varepsilon = \ldots$\stratis{fix me}. In addition, we prove the following lower bound. \begin{theorem}\label{thm:lowerbound} -There is no $2$-approximate, truthful, budget feasible, individionally rational mechanism for EDP. +There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} %\stratis{move the proof as appropriate} \begin{proof} |