首页    期刊浏览 2024年12月05日 星期四
登录注册

文章基本信息

  • 标题:Partial Function Extension with Applications to Learning and Property Testing
  • 本地全文:下载
  • 作者:Umang Bhaskar ; Gunjan Kumar
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:181
  • 页码:1-16
  • DOI:10.4230/LIPIcs.ISAAC.2020.46
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory. Here, we are given a partial function consisting of n points from a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a function defined on the domain, that additionally satisfies a given property, such as linearity. We formally study partial function extension to fundamental properties in combinatorial optimization - subadditivity, XOS, and matroid independence. A priori, it is not clear if partial function extension for these properties even lies in NP (or coNP). Our contributions are twofold. Firstly, for the properties studied, we give bounds on the complexity of partial function extension. For subadditivity and XOS, we give tight bounds on approximation guarantees as well. Secondly, we develop new connections between partial function extension and learning and property testing, and use these to give new results for these problems. In particular, for subadditive functions, we give improved lower bounds on learning, as well as the first subexponential-query tester.
  • 关键词:Partial function extension; subadditivity; matroid rank; approximation algorithms; learning; property testing
国家哲学社会科学文献中心版权所有