Bhaskar, Umang ;
Kumar, Gunjan
The Complexity of Partial Function Extension for Coverage Functions
Abstract
Coverage functions are an important subclass of submodular functions, finding applications in machine learning, game theory, social networks, and facility location. We study the complexity of partial function extension to coverage functions. That is, given a partial function consisting of a family of subsets of [m] and a value at each point, does there exist a coverage function defined on all subsets of [m] that extends this partial function? Partial function extension is previously studied for other function classes, including boolean functions and convex functions, and is useful in many fields, such as obtaining bounds on learning these function classes.
We show that determining extendibility of a partial function to a coverage function is NPcomplete, establishing in the process that there is a polynomialsized certificate of extendibility. The hardness also gives us a lower bound for learning coverage functions. We then study two natural notions of approximate extension, to account for errors in the data set. The two notions correspond roughly to multiplicative pointwise approximation and additive L_1 approximation. We show upper and lower bounds for both notions of approximation. In the second case we obtain nearly tight bounds.
BibTeX  Entry
@InProceedings{bhaskar_et_al:LIPIcs:2019:11245,
author = {Umang Bhaskar and Gunjan Kumar},
title = {{The Complexity of Partial Function Extension for Coverage Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {30:130:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11245},
URN = {urn:nbn:de:0030drops112457},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.30},
annote = {Keywords: Coverage Functions, PAC Learning, Approximation Algorithm, Partial Function Extension}
}
2019
Keywords: 

Coverage Functions, PAC Learning, Approximation Algorithm, Partial Function Extension 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

2019 