2026-07-26T11:41:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18101 2024-03-06T11:01:01Z ddc:004 open_access

An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets Doron-Arad, Ilan Kulik, Ariel Shachnai, Hadas budgeted matching budgeted matroid intersection efficient polynomial-time approximation scheme 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, Vondrák 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 ε, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilan Doron-Arad and Ariel Kulik and Hadas Shachnai 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.49 urn:nbn:de:0030-drops-181018 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.49 eng https://creativecommons.org/licenses/by/4.0/legalcode