His homepage: https://sites.google.com/site/arielkulik/

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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

Zoom

897 027 2575

passcode not visible

logged in users only