CISPA
Browse

File(s) not publicly available

An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets

conference contribution
posted on 2023-11-29, 18:24 authored by Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondrak and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit a fully PTAS (FPTAS), or even an efficient PTAS (EPTAS). In this paper we answer the second part of this question affirmatively, by presenting an EPTAS for budgeted matching and budgeted matroid intersection. A main component of our scheme is a construction of representative sets for desired solutions, whose cardinality depends only on $\eps$, the accuracy parameter. Thus, enumerating over solutions within a representative set leads to an EPTAS. This crucially distinguishes our algorithms from previous approaches, which rely on exhaustive enumeration over the solution set.

History

Preferred Citation

Ilan Doron-Arad, Ariel Kulik and Hadas Shachnai. An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets. In: International Colloquium on Automata, Languages and Programming (ICALP). 2023.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Colloquium on Automata, Languages and Programming (ICALP)

Legacy Posted Date

2023-05-05

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3940, title = "An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets", author = "Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas", booktitle="{International Colloquium on Automata, Languages and Programming (ICALP)}", year="2023", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC