Talks
Fall 2018

A Fast Algorithm for Computing the Maximum Weight Base in a Linear Matroid

Thursday, September 27th, 2018 11:00 am11:30 am

Add to Calendar

Speaker: 

Huy Nguyen (Northeastern University)

A fundamental algorithmic result for matroids is that the maximum weight base can be computed using the greedy algorithm. For linear matroids, an important question is the time complexity of computing such a base. In this work, we give a fast algorithm that computes the same output as the greedy algorithm for linear matroids.