Seminars
View all Seminars | Download ICal for this eventA Weighted-to-Unweighted Reduction for Matroid Intersection
Series: Bangalore Theory Seminars
Speaker: Aditi Dudeja, CUHK-Shenzhen
Date/Time: Aug 20 11:00:00
Location: CSA Auditorium, (Room No. 104, Ground Floor)
Abstract:
Given two matroids M1 and M2 over the same ground set, the matroid intersection problem is to find the maximum cardinality common independent set. In the weighted version of the problem, the goal is to find a maximum weight common independent set. It has been a matter of interest to find efficient approximation algorithms for this problem in various settings. In many of these models, there is a gap between the best known results for the unweighted and weighted versions.
In this work, we address the question of closing this gap. Our main result is a reduction which converts any α-approximate unweighted matroid intersection algorithm into an α(1??ε)-approximate weighted matroid intersection algorithm, while increasing the runtime of the algorithm by a logW factor, where W is the aspect ratio. Our framework is versatile and translates to settings such as streaming and one-way communication complexity where matroid intersection is well-studied. As a by-product of our techniques, we derive new results for weighted matroid intersection in these models.
Microsoft Teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: KVN Sreenivas, Sreeramji K S, Ritabrata Barat, Venkata Sai Nikhil Srivatsava Ayyadevara