Recognizing Coverage Functions

DOI10.1137/140964072zbMath1329.68280OpenAlexW1775056764MaRDI QIDQ2944461

Deeparnab Chakrabarty, Zhi-Yi 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

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

Related Items (2)

The Complexity of Partial Function Extension for Coverage Functions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Is submodularity testable?
• Combinatorial auctions with decreasing marginal utilities
• Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
• Testing Coverage Functions
• Property testing and its connection to learning and approximation
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• On proximity oblivious testing
• From convex optimization to randomized mechanisms
• Learning submodular functions
• Limitations of Randomized Mechanisms for Combinatorial Auctions

This page was built for publication: Recognizing Coverage Functions