The Taub Faculty of Computer Science Events and Talks

Abstract: We consider the 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 multi-budgeted matroid 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 our work. Our main contribution is an EPTAS for the budgeted matroid independent set problem, and a generalization of the technique for obtaining an EPTAS for budgeted matching and budgeted matroid intersection. A key idea of the scheme is to find a representative set for the instance, whose cardinality depends solely on 1/\eps, where \eps>0 is the accuracy parameter of the scheme. Our scheme enumerates over subsets of the representative set and extends each subset using Lagrangian relaxation techniques. For a single matroid, the representative set is identified via a matroid basis minimization, which can be solved by a simple greedy approach. For matching and matroid intersection, matroid basis minimization is used as a baseline for a more sophisticated approach.