Nonlinear matroid optimization and experimental design

View/ Open
Date
2007-03-24MFO Scientific Program
Research in Pairs 2007Series
Oberwolfach Preprints;2007,06Author
Lee, Jon
Onn, Shmuel
Weismantel, Robert
Berstein, Yael
Maruri-Aguilar, Hugo
Riccomagno, Eva
Wynn, Henry P.
Metadata
Show full item recordOWP-2007-06
Abstract
We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multi-criteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection, and an algebraic algorithm for vectorial matroids. Our work is partly motivated by applications to minimum-aberration model-fitting in experimental design in statistics, which we discuss and demonstrate in detail.