From query complexity to computational complexity
From MaRDI portal
Publication:5415538
DOI10.1145/2213977.2214076zbMath1286.68225OpenAlexW2027680861MaRDI QIDQ5415538
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.307.3011
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26)
Related Items (12)
Streaming Algorithms for Submodular Function Maximization ⋮ A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Robust Monotone Submodular Function Maximization ⋮ Learning in auctions: regret is hard, envy is easy ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Exact learning of multitrees and almost-trees using path queries ⋮ Unnamed Item ⋮ Truthful mechanism design via correlated tree rounding ⋮ Economic efficiency requires interaction ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Robust monotone submodular function maximization ⋮ Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
This page was built for publication: From query complexity to computational complexity
