On Optimization and Counting of Non-Broken Bases of Matroids

Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan

Given a matroid $M=(E,\mathcal{I})$, and a total ordering over the elements $E$, a broken circuit is a circuit where the smallest element is removed and an NBC independent set is an i…