Campus Event Calendar

Event Entry

What and Who

Algorithms and Hardness for the Budgeted Matroid Independent Set problem

Ariel Kulik
The Technion, Israel
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 9 April 2024
30 Minutes
E1 4


Both the classic knapsack problem and maximum matroid independent set appear in a wide range of applications. In some cases, both a matroid and a knapsack constraint appear together, as in Multiple-Choice Knapsack and Knapsack with Cardinality Constraint. The talk will focus on the budgeted matroid independent set problem which adds a matroid independence constraint to the classic knapsack problem. The input is a ground set of elements, where each element has a cost and a profit, along with a matroid over the elements and a budget. The goal is to select a maximum profit independent set of the matroid whose total cost is bounded by the budget.

I will show how to attain an Efficient Polynomial Time Approximation Scheme (EPTAS) for the problem, improving upon the previous Polynomial Time Approximation Schemes (PTAS) [Grandoni and Zenklusen 10', Berger, Bonifaci, Grandoni and Schäfer, 08'].
The speed-up is attained via efficient enumeration which relies on the combinatorial structure of the matroid and replaces the naive enumeration used by previous algorithms. The algorithmic result will be complemented by a lower bound showing the problem does not admit a Fully Polynomial Time Approximation Scheme (FPTAS), indicating the algorithm cannot be improved for general matroids and motivating future research to focus on restricted families of matroids.


Nidhi Rathi
+49 681 9325 1134
--email hidden

Virtual Meeting Details

897 027 2575
passcode not visible
logged in users only

Nidhi Rathi, 03/26/2024 13:44
Nidhi Rathi, 03/15/2024 13:07
Nidhi Rathi, 02/29/2024 12:38
Nidhi Rathi, 02/28/2024 12:10 -- Created document.