Seminars

View all Seminars  |  Download ICal for this event

Determinant Maximization via Matroid Intersection Algorithms

Series: Bangalore Theory Seminars

Speaker: Aditi Laddha Georgia Institute of Technology

Date/Time: Oct 14 11:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics, convex geometry, fair allocations, combinatorics, spectral graph theory, network design, and random processes. In an instance of a determinant maximization problem, we are given a collection of vectors $U = {v_1, ldots, v_n}$ in $d$ dimensions, and a goal is to pick a subset S �?? U of given vectors to maximize the determinant of the matrix $sum_{i in S} v_i v_i^T$. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint ($|S| leq k$) or matroid constraint ($S$ is a basis of a matroid defined on the vectors). In this talk, we give a polynomial-time deterministic algorithm that returns an $r^{O(r)}$-approximation for any matroid of rank $r leq d$. Our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improves any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the determinant function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

Organizers Note: Joint work with Adam Brown, Madhusudhan Pittu, Mohit Singh, and Prasad Tetali.

For more details please visit: Link

Microsoft teams link:

Link




Hosts: Rahul Madhavan and Rameesh Paul