Recognizing coverage functions

DOI10.1137/140964072zbMATH Open1329.68280OpenAlexW1775056764MaRDI QIDQ2944461FDOQ2944461

Authors: Deeparnab Chakrabarty, Zhiyi Huang 

Publication date: 2 September 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10722/217771

Recommendations

• Testing coverage functions
• Is submodularity testable?
• Testing submodularity and other properties of valuation functions
• Optimization with uniform size queries
• Sketching valuation functions

zbMATH Keywords

learningproperty testingFarkas lemmacoverage functions

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Property testing and its connection to learning and approximation
• Is submodularity testable?
• Combinatorial auctions with decreasing marginal utilities
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Combinatorial auctions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing coverage functions
• Learning submodular functions
• From convex optimization to randomized mechanisms
• Title not available (Why is that?)
• Title not available (Why is that?)
• On proximity oblivious testing
• Limitations of Randomized Mechanisms for Combinatorial Auctions
• Optimal bounds on approximation of submodular and XOS functions by juntas

Cited In (3)

• Title not available (Why is that?)
• The Complexity of Partial Function Extension for Coverage Functions
• Testing coverage functions

This page was built for publication: Recognizing coverage functions

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