Recognizing coverage functions

DOI10.1137/140964072MaRDI QIDQ2944461zbMATH OpenOpenAlexFDO

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

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 5968956 (Why is no real title available?)
• scientific article; zbMATH DE number 1241385 (Why is no real title available?)
• scientific article; zbMATH DE number 1482142 (Why is no real title available?)
• scientific article; zbMATH DE number 3394280 (Why is no real title available?)
• Combinatorial auctions
• Combinatorial auctions with decreasing marginal utilities
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• From convex optimization to randomized mechanisms, toward optimal combinatorial auctions
• Is submodularity testable?
• Learning submodular functions
• Limitations of randomized mechanisms for combinatorial auctions
• On proximity oblivious testing
• Optimal bounds on approximation of submodular and XOS functions by juntas
• Property testing and its connection to learning and approximation
• Sketching valuation functions
• Testing coverage functions

Cited in

(4)

• The Complexity of Partial Function Extension for Coverage Functions
• Monotonic decompositions of submodular set functions
• Testing submodularity and other properties of valuation 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)