Testing coverage functions

DOI10.1007/978-3-642-31594-7_15MaRDI QIDQ2843245zbMATH OpenOpenAlexFDO

Authors Deeparnab Chakrabarty, Zhiyi Huang

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.1587

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: A coverage function f over a ground set [m] is associated with a universe U of weighted elements and m subsets A_1,..., A_m of U, and for any subset T of [m], f(T) is defined as the total weight of the elements in the union $cu{p}_{jinT}{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. Set functions such as coverage functions often lack succinct representations, and in algorithmic applications, an access to a value oracle is assumed. In this paper, we ask whether one can test 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 gives a polytime tester for succinct coverage functions for which |U$ is polynomially bounded in m. In contrast, we demonstrate a set function which is "far" from coverage, but requires 2^{ ilde{Theta}(m)} queries to distinguish it from the class of coverage functions.

Recommendations

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

Cited in

(9)

• Approximate tradeoffs on weighted labeled matroids
• Recognizing coverage functions
• Testing submodularity and other properties of valuation functions
• Is submodularity testable?
• Approximate F₂-Sketching of Valuation Functions
• The Limitations of Optimization from Samples
• Approximating submodular \(k\)-partition via principal partition sequence
• Monotonic decompositions of submodular set functions
• A direct proof of the characterization of the convexity of the discrete Choquet integral

This page was built for publication: Testing coverage functions

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