Theory Seminar, Wednesday Feb 28: Hadas Shachnai (Technion) - Recent Advances in Matroid Constrained Optimization

[Arnold Filtser]

Hi all,

Next week (Wed Feb 28, at 12:00) we will meet for our theory seminar.

Location: Building 503 room 226.

See you all there,

Arnold and Talya

https://theory.cs.biu.ac.il/

Speaker: Hadas Shachnai (Technion)
Title: Recent Advances in Matroid Constrained Optimization
Abstract:  A wide range of NP-hard combinatorial optimization problems can be formulated as follows. We are given a ground set E and a family M of subsets of E called the {\em feasible sets}. Each element in the ground set is associated with a non-negative cost, and some profit. Also, we have a budget B. We seek a feasible set S in M of total cost at most B which maximizes the profit. I will discuss recent results for several prominent problems in this class, including {\em budgeted matching}, {\em budgeted matroid independent set}, and {\em budgeted matroid intersection}. While all of the problems admit {\em polynomial-time approximation schemes} (PTAS), it has been an intriguing open question whether these problems admit {\em efficient} PTAS (EPTAS). We answer this question affirmatively, by presenting EPTASs for all problems. We further show that {\em budgeted matroid independent set}, and {\em budgeted matroid intersection} do not admit a {\em fully} PTAS, thus resolving the complexity status of these problems. Our EPTASs are based on a new framework of {\em represenative sets}, and for the  hardness results we introduce a new family of {\em paving matroids}, which are of independent interest. 
Based on joint papers with Ilan Doron-Arad and Ariel Kulik.

[Arnold Filtser]

The seminar starts in one hour! 

See you all there.