Document Open Access Logo

The Complexity of Partial Function Extension for Coverage Functions

Authors Umang Bhaskar, Gunjan Kumar

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.30.pdf
  • Filesize: 0.53 MB
  • 21 pages

Document Identifiers

Author Details

Umang Bhaskar
  • Tata Institute of Fundamental Research, Mumbai, India
Gunjan Kumar
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

  • Bhaskar, Umang: Supported in part by a Ramanujan fellowship and an Early Career Research award.

Cite As Get BibTex

Umang Bhaskar and Gunjan Kumar. The Complexity of Partial Function Extension for Coverage Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.30

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 NP-complete, establishing in the process that there is a polynomial-sized 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 point-wise 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Coverage Functions
  • PAC Learning
  • Approximation Algorithm
  • Partial Function Extension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden. Sketching valuation functions. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1025-1035. Society for Industrial and Applied Mathematics, 2012. Google Scholar
  2. Maria-Florina Balcan and Nicholas J. A. Harvey. Learning submodular functions. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 793-802, 2011. Google Scholar
  3. Eric Balkanski, Aviad Rubinstein, and Yaron Singer. The limitations of optimization from samples. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1016-1027. ACM, 2017. Google Scholar
  4. Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997. Google Scholar
  5. Umang Bhaskar and Gunjan Kumar. Partial Function Extension with Applications to Learning and Property Testing. arXiv preprint, 2018. URL: http://arxiv.org/abs/1812.05821.
  6. Liad Blumrosen and Noam Nisan. Combinatorial auctions. Algorithmic game theory, 267:300, 2007. Google Scholar
  7. Paul S. Bonsma, Hajo Broersma, Viresh Patel, and Artem V. Pyatkin. The Complexity Status of Problems Related to Sparsest Cuts. In Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, pages 125-135, 2010. Google Scholar
  8. Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 946-957. SIAM, 2014. Google Scholar
  9. Endre Boros, Toshihide Ibaraki, and Kazuhisa Makino. Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions. Inf. Comput., 140(2):254-283, 1998. Google Scholar
  10. Deeparnab Chakrabarty and Zhiyi Huang. Recognizing Coverage Functions. SIAM J. Discrete Math., 29(3):1585-1599, 2015. Google Scholar
  11. Gerard Cornuejols, Marshall L Fisher, and George L Nemhauser. Exceptional paper—Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management science, 23(8):789-810, 1977. Google Scholar
  12. F Dragomirescu and C Ivan. The smallest convex extensions of a convex function. Optimization, 24(3-4):193-206, 1992. Google Scholar
  13. Vitaly Feldman and Pravesh Kothari. Learning coverage functions and private release of marginals. In Conference on Learning Theory, pages 679-702, 2014. Google Scholar
  14. Rafael M. Frongillo and Ian A. Kash. General Truthfulness Characterizations via Convex Analysis. In Web and Internet Economics - 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, pages 354-370, 2014. Google Scholar
  15. Chris Godsil and Gordon F Royle. Algebraic graph theory, volume 207. Springer Science & Business Media, 2013. Google Scholar
  16. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012. Google Scholar
  17. Subhash Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Proceedings 2001 IEEE International Conference on Cluster Computing, pages 600-609. IEEE, 2001. Google Scholar
  18. Andreas Krause, H Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Robust submodular observation selection. Journal of Machine Learning Research, 9(Dec):2761-2801, 2008. Google Scholar
  19. Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-296, 2006. Google Scholar
  20. Hans JM Peters and Peter P Wakker. Convex functions on non-convex domains. Economics letters, 22(2-3):251-255, 1986. Google Scholar
  21. Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. J. ACM, 35(4):965-984, 1988. Google Scholar
  22. Lior Seeman and Yaron Singer. Adaptive seeding in social networks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 459-468. IEEE, 2013. Google Scholar
  23. C. Seshadhri and Jan Vondrák. Is Submodularity Testable? Algorithmica, 69(1):1-25, 2014. Google Scholar
  24. Donald M Topkis. Minimizing a submodular function on a lattice. Operations research, 26(2):305-321, 1978. Google Scholar
  25. Armin Uhlmann. Roofs and convexity. Entropy, 12(7):1799-1832, 2010. Google Scholar
  26. Min Yan. Extension of convex function. arXiv preprint, 2012. To appear in the Journal of Convex Analysis. URL: http://arxiv.org/abs/1207.0944.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact