File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Recognizing Coverage Functions

TitleRecognizing Coverage Functions
Authors
KeywordsCoverage functions
Farkas lemma
Learning
Property testing
Issue Date2015
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php
Citation
SIAM Journal on Discrete Mathematics, 2015, v. 29 n. 3, p. 1585-1599 How to Cite?
AbstractA coverage function $f$ over a ground set $[m]$ is associated with a universe $U$ of weighted elements and $m$ sets $A_1,ldots,A_m subseteq U$, and for any $Tsubseteq [m]$, $f(T)$ is defined as the total weight of the elements in the union $cup_{jin T} A_j$. Coverage functions are an important special case of submodular functions, and arise in many applications, for instance, as a class of utility functions of agents in combinatorial auctions. Naïve representations of coverage functions have size exponential in $m$, and in algorithmic applications, an access to a value oracle is assumed. In this paper, we ask whether one can recognize if a given oracle is that of a coverage function or not. We demonstrate an algorithm which makes $O(m|U|)$ queries to an oracle of a coverage function and completely reconstructs it. This is polynomial time whenever $|U|$ is polynomially bounded implying the function has a succinct description. To complement the above result, we show a negative result. We prove that “noncoverageness” needs large certificates---there exists a function which is not coverage and yet any algorithm making fewer than $2^{m-1}$ queries cannot distinguish this function from some coverage function. Our positive result shows that the property of coverageness has $O(m|U|)$-query proximity oblivious testers, while our negative result shows an exponential lower bound. We believe our lower bound also goes through for general property testers, and provide some evidence of the same.
Persistent Identifierhttp://hdl.handle.net/10722/217771
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 1.031
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChakrabarty, D-
dc.contributor.authorHuang, Z-
dc.date.accessioned2015-09-18T06:12:44Z-
dc.date.available2015-09-18T06:12:44Z-
dc.date.issued2015-
dc.identifier.citationSIAM Journal on Discrete Mathematics, 2015, v. 29 n. 3, p. 1585-1599-
dc.identifier.issn0895-4801-
dc.identifier.urihttp://hdl.handle.net/10722/217771-
dc.description.abstractA coverage function $f$ over a ground set $[m]$ is associated with a universe $U$ of weighted elements and $m$ sets $A_1,ldots,A_m subseteq U$, and for any $Tsubseteq [m]$, $f(T)$ is defined as the total weight of the elements in the union $cup_{jin T} A_j$. Coverage functions are an important special case of submodular functions, and arise in many applications, for instance, as a class of utility functions of agents in combinatorial auctions. Naïve representations of coverage functions have size exponential in $m$, and in algorithmic applications, an access to a value oracle is assumed. In this paper, we ask whether one can recognize if a given oracle is that of a coverage function or not. We demonstrate an algorithm which makes $O(m|U|)$ queries to an oracle of a coverage function and completely reconstructs it. This is polynomial time whenever $|U|$ is polynomially bounded implying the function has a succinct description. To complement the above result, we show a negative result. We prove that “noncoverageness” needs large certificates---there exists a function which is not coverage and yet any algorithm making fewer than $2^{m-1}$ queries cannot distinguish this function from some coverage function. Our positive result shows that the property of coverageness has $O(m|U|)$-query proximity oblivious testers, while our negative result shows an exponential lower bound. We believe our lower bound also goes through for general property testers, and provide some evidence of the same.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php-
dc.relation.ispartofSIAM Journal on Discrete Mathematics-
dc.rights© 2015 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Discrete Mathematics in volume 29, issue 3, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectCoverage functions-
dc.subjectFarkas lemma-
dc.subjectLearning-
dc.subjectProperty testing-
dc.titleRecognizing Coverage Functions-
dc.typeArticle-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/140964072-
dc.identifier.scopuseid_2-s2.0-84943147704-
dc.identifier.hkuros253937-
dc.identifier.volume29-
dc.identifier.issue3-
dc.identifier.spage1585-
dc.identifier.epage1599-
dc.identifier.isiWOS:000362419600024-
dc.publisher.placeUnited States-
dc.identifier.issnl0895-4801-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats