| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10523906 | Operations Research Letters | 2016 | 5 Pages |
Abstract
We show that finding lexicographically minimal n bases in a matroid can be done in polynomial time in the oracle model. This follows from a more general result that the shifted optimization problem over a matroid can be solved in polynomial time as well. We also solve these problems for intersections of strongly base orderable matroids.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Asaf Levin, Shmuel Onn,