diff options
Diffstat (limited to 'related.tex')
| -rw-r--r-- | related.tex | 12 |
1 files changed, 5 insertions, 7 deletions
diff --git a/related.tex b/related.tex index 6cf059f..b25b91b 100644 --- a/related.tex +++ b/related.tex @@ -19,12 +19,11 @@ full-information setup, Chen \emph{et al.},~propose a truthful, $8.34$-approxima \paragraph{Budget Feasible Mechanism Design on Specific Problems} Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. -The above deterministic mechanisms for \textsc{Knapsack} \cite{chen} and +The deterministic mechanisms for \textsc{Knapsack} \cite{chen} and \textsc{Coverage} \cite{singer-influence} follow the same general framework, -which we also employ. We describe this framework in detail in +which we also employ in our mechanism for \EDP. We describe this framework in detail in Section~\ref{sec:main}. Both of these mechanisms rely on approximating the -optimal solution to the underlying combinatorial problem by a well-known LP -relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No +optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No such relaxation exists for \EDP, whose logarithmic objective is unlikely to be approximable through an LP. We develop instead a convex relaxation to \EDP; though, contrary to the above LP relaxations, this cannot be solved exactly, we @@ -47,12 +46,11 @@ in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughm in which an auctioneer aims at maximizing a set function which is the sum of utilities of strategic bidders (\emph{i.e.}, the social welfare). As noted by \citeN{archer-approximate}, approximations to this maximization must preserve incentive compatibility and truthfulness. Most approximation algorithms do not preserve these properties, hence specific relaxations, and corresponding roundings to an integral solution, must be -constructed. \citeN{archer-approximate} propose a randomized rounding of the linear -programming relaxation of the \textsc{SetPacking} problem, yielding a mechanism +constructed. \citeN{archer-approximate} propose a randomized rounding of the LP relaxation of the \textsc{SetPacking} problem, yielding a mechanism which is \emph{truthful-in-expectation}. %and in high probability. \citeN{lavi-truthful} construct randomized truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation -ratio in \cite{archer-approximate}, by treating the fractional solution of a linear program as a probability distribution over integral solutions. +ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution over integral solutions. Beyond LP relaxations, \citeN{dughmi2011convex} propose |