An EPTAS for budgeted matching, budgeted matroid independent set, and budgeted matroid intersection via representative sets

• 成果类型: Article; Early Access
• 署名作者: Doron-Arad, Ilan; Kulik, Ariel; Shachnai, Hadas
• 署名单位: Technion Israel Institute of Technology; Ben-Gurion University of the Negev
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02397-3
• 发表日期: 2026-07-30
• 关键词: algorithms

摘要

We study the budgeted versions of the well known matching, matroid independent set, and matroid intersection problems. While all problems admit polynomial-time approximation schemes (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondr & aacute;k and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit an efficient PTAS (EPTAS). In this paper, we answer this question affirmatively, by presenting an EPTAS for budgeted matching, budgeted matroid independent set, and budgeted matroid intersection. As we recently showed that budgeted matroid independent set and budgeted matroid intersection do not admit a fully PTAS (FPTAS), this paper resolves the complexity status of the two problems. The running times of previous schemes for these problems are dominated by exhaustive enumeration over the O1 epsilon most profitable elements in an optimal solution, where epsilon is the accuracy parameter. We replace this enumeration with a new framework of representative sets, in which we enumerate over subsets of a representative set of cardinality that depends only on epsilon .