Optimization with Demand Oracles
Optimization with Demand Oracles
复制标题
使用需求预言机进行优化
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Sigal Oren
中科院分区：
文献类型：
--
作者：
Ashwinkumar Badanidiyuru;Shahar Dobzinski;Sigal Oren
我们研究预算约束下的最大化问题，其中我们给定一个估价函数v，预算B和每个项目i的成本$$c_i$$ci。目标是找到一个集合S，使v（S）最大化，但须满足$$Sigma _{iin S}c_ile B$$Σi∈Sci≤B。这个问题的特殊情况是充分研究的问题，从子模块优化。特别地，当成本都相等（基数约束）时，Nemhauser等人的经典结果表明贪婪算法提供了$$frac{e}{e-1}$$ee-1近似。大量的文献，利用需求查询，以引起代理人在经济环境中的偏好的动机，我们开发的算法，保证改进的近似比的存在下，需求预言。我们能够打破$$frac{e}{e-1}$$ee-1障碍：我们提出的算法，只使用多项式许多需求查询，并有近似比$$frac{9}{8}+$$98+$frac{9}{8}的一般问题和$$frac{9}{8}$$98的最大化受到基数约束。我们还考虑了更一般的次可加赋值类。这里，如果赋值只能通过值查询访问，则只能保证平凡的近似比。相比之下，我们提出的算法，使用需求查询，并获得近似比$2 +$$2+$$2的一般问题和2的最大化受到基数约束。即使估值是非单调的，我们也保证这些近似比。我们表明，这些比率基本上是最优的，在这个意义上说，对于任何常数$
We study maximization subject to a budget constraint, where we are given a valuation function v, budget B and a cost $$c_i$$ci for each item i. The goal is to find a set S that maximizes v(S) subject to $$Sigma _{iin S}c_ile B$$Σi∈Sci≤B. Special cases of this problem are well-studied problems from submodular optimization. In particular, when the costs are all equal (cardinality constraint), a classic result by Nemhauser et al. shows that the greedy algorithm provides an $$frac{e}{e-1}$$ee-1 approximation. Motivated by a large body of literature that utilizes demand queries to elicit the preferences of agents in economic settings, we develop algorithms that guarantee improved approximation ratios in the presence of demand oracles. We are able to break the $$frac{e}{e-1}$$ee-1 barrier: we present algorithms that use only polynomially many demand queries and have approximation ratios of $$frac{9}{8}+epsilon $$98+ϵ for the general problem and $$frac{9}{8}$$98 for maximization subject to a cardinality constraint. We also consider the more general class of subadditive valuations. Here, if the valuations can only be accessed by value queries, only trivial approximation ratios can be guaranteed. In contrast, we present algorithms that use demand queries and obtain an approximation ratio of $$2+epsilon $$2+ϵ for the general problem and 2 for maximization subject to a cardinality constraint. We guarantee these approximation ratios even when the valuations are non-monotone. We show that these ratios are essentially optimal, in the sense that for any constant $$epsilon >0$$ϵ>0, obtaining an approximation ratio of $$2-epsilon $$2-ϵ requires exponentially many demand queries.