אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We study budgeted variants of the well known Matching, Matroid Independent Set, and Matroid Intersection problems. While the three problems admit polynomial-time approximation schemes (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 work, we show 
that the three problems admit an EPTAS. On the other hand, we rule out the existence of an FPTAS for Budgeted Matroid Independent Set and Budgeted Matroid Intersection, thus resolving the complexity status of the last two problems.

We extend our lower bounds to the more general family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a linear objective function subject to (i) a matroid independent set, or a matroid basis constraint, (ii) an additional linear constraint. We show that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well studied problems, including Constrained Minimum Basis of a Matroid and Knapsack Cover with a Matroid Constraint.

Our EPTASs rely on the novel representative set technique in which we replace exhaustive enumeration over a given input by enumeration over a relatively small subset of elements. We obtain our lower bounds for MOL problems by showing first that the classic Exact Weight Matroid Basis (EMB) problem does not admit a pseudo-polynomial time algorithm. This distinguishes EMB from the special cases of k-subset sum and EMB on a linear matroid, which are solvable in pseudo-polynomial time.