From query complexity to computational complexity

DOI10.1145/2213977.2214076MaRDI QIDQ5415538zbMATH OpenOpenAlexFDO

Authors Shahar Dobzinski, Jan Vondrák

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

zbMATH Keywords

computational complexityinapproximabilitysubmodular function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Symmetry and approximability of submodular maximization problems
• Improved inapproximability for submodular maximization
• Maximizing Non-monotone Submodular Functions
• The submodular welfare problem with demand queries
• Communication complexity of combinatorial auctions with submodular valuations

Cited in

(18)

• On the Computational Power of Querying the History
• Maximizing sums of non-monotone submodular and linear functions: understanding the unconstrained case
• Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Robust monotone submodular function maximization
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• Economic efficiency requires interaction
• Approximate Query Complexity
• Limitations of randomized mechanisms for combinatorial auctions
• Learning in auctions: regret is hard, envy is easy
• Robust monotone submodular function maximization
• Monotone submodular multiway partition
• An algorithmic framework for black-box reductions from Bayesian mechanism design to algorithm design
• Streaming algorithms for submodular function maximization
• The query complexity of certification
• scientific article; zbMATH DE number 7651142 (Why is no real title available?)
• Exact learning of multitrees and almost-trees using path queries
• Truthful mechanism design via correlated tree rounding

This page was built for publication: From query complexity to computational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415538)