From query complexity to computational complexity
From query complexity to computational complexity
复制标题
从查询复杂度到计算复杂度
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
J. Vondrák
中科院分区：
文献类型：
--
作者：
Shahar Dobzinski;J. Vondrák
我们考虑子模优化问题，并提供一种将对称间隙技术产生的预言不可逼近性结果转换为计算复杂性不可逼近性结果的通用方法，其中子模函数是明确给出的（假设 NP ≠ RP）。我们技术的应用包括用于最大化对称非负子模函数的最佳计算硬度（1/2 + ε）近似、用于在具有 k 个子模投标人（对于常数 k）的组合拍卖中福利最大化的最佳硬度近似（1-（1-1/k）k + ε）、用于在拟阵基上最大化非负子模函数的超常数硬度以及更严格的边界最大化受基数约束的单调子模函数。与绝大多数计算不可近似性结果不同，我们的方法不使用 PCP 机制或 Unique Games 猜想，而是依赖于使用列表可解码代码从 Unique-SAT 直接还原。
We consider submodular optimization problems, and provide a general way of translating oracle inapproximability results arising from the symmetry gap technique to computational complexity inapproximability results, where the submodular function is given explicitly (under the assumption that NP ≠ RP). Applications of our technique include an optimal computational hardness of (1/2 + ε)-approximation for maximizing a symmetric nonnegative submodular function, an optimal hardness of (1-(1-1/k)k + ε)-approximation for welfare maximization in combinatorial auctions with k submodular bidders (for constant k), super-constant hardness for maximizing a nonnegative submodular function over matroid bases, and tighter bounds for maximizing a monotone submodular function subject to a cardinality constraint. Unlike the vast majority of computational inapproximability results, our approach does not use the PCP machinery or the Unique Games Conjecture, but relies instead on a direct reduction from Unique-SAT using list-decodable codes.