Fall 2018

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

Thursday, Sep. 27, 2018 11:00 am11:30 am

Add to Calendar


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.