CISPA
Browse

File(s) not publicly available

An EPTAS for Budgeted Matroid Independent Set

conference contribution
posted on 2023-11-29, 18:25 authored by Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We consider the {\em budgeted matroid independent set} problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a matroid over the elements and a budget. The goal is to select a subset of elements which maximizes the total profit subject to the matroid and budget constraints. Several well known special cases, where we have, e.g., a uniform matroid and a budget, or no matroid constraint (i.e., the classic knapsack problem), admit a fully polynomial-time approximation scheme (FPTAS). In contrast, already a slight generalization to the {\em multi-budgetedmatroid independent set} problem has a PTAS but does not admit an efficient polynomial-time approximation scheme (EPTAS). This implies a PTAS for our problem, which is the best known result prior to this work. Our main contribution is an EPTAS for the budgeted matroid independent set problem. A key idea of the scheme is to find a {\em representative set} for the instance, whose cardinality depends solely on $1/\eps$, where $\eps >0$ is the accuracy parameter of the scheme. The representative set is identified via matroid basis minimization, which can be solved by a simple greedy algorithm. Our scheme enumerates over subsets of the representative set and extends each subset using a linear program. The notion of representative sets may be useful in solving other variants of the budgeted matroid independent set problem.

History

Preferred Citation

Ilan Doron-Arad, Ariel Kulik and Hadas Shachnai. An EPTAS for Budgeted Matroid Independent Set. In: Symposium on Simplicity in Algorithms (SOSA). 2023.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Symposium on Simplicity in Algorithms (SOSA)

Legacy Posted Date

2023-05-05

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3939, title = "An EPTAS for Budgeted Matroid Independent Set", author = "Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas", booktitle="{Symposium on Simplicity in Algorithms (SOSA)}", year="2023", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC