Scholarlink

<p>We study the budgeted versions of the well known matching, matroid independent set, and matroid intersection problems. While all problems admit <i>polynomial-time approximation schemes (PTAS)</i> [Berger et al. (Math. Programming, 2011), Chekuri, Vondrák and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit an <i>efficient</i> PTAS (EPTAS). In this paper, we answer this question affirmatively, by presenting an EPTAS for <i>budgeted matching</i>, <i>budgeted matroid independent set</i>, and <i>budgeted matroid intersection</i>. As we recently showed that budgeted matroid independent set and budgeted matroid intersection do not admit a <i>fully</i> 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O\left( \frac{1}{{\varepsilon }}\right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mfenced close=")" open="("> <mfrac> <mn>1</mn> <mi>ε</mi> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation> most profitable elements in an optimal solution, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({\varepsilon }\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> is the accuracy parameter. We replace this enumeration with a new framework of <i>representative sets</i>, in which we enumerate over subsets of a <i>representative set</i> of cardinality that depends only on <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\({\varepsilon }\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2026年7月30日

查看全文
  • Ilan Doron-Arad,
  • Ariel Kulik,
  • Hadas Shachnai

摘要

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á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 \(O\left( \frac{1}{{\varepsilon }}\right) \) O 1 ε most profitable elements in an optimal solution, where \({\varepsilon }\) ε 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 \({\varepsilon }\) ε .