Nonlinear Matroid Optimization and Experimental Design

Yael Berstein(yaelbertx.technion.ac.il)
Jon Lee(jonleeus.ibm.com)
Hugo Maruri-Aguilar(h.maruri-aguilarlse.ac.uk)
Shmuel Onn(onnie.technion.ac.il)
Eva Riccomagno(riccomagnodima.unige.it)
Robert Weismantel(weismantelimo.math.uni-magdeburg.de)
Henry Wynn(h.wynnlse.ac.uk)

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.

Keywords: aberration, matroid intersection, combinatorial optimization, matroid, nonlinear, experimental design

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Nonlinear Optimization (Other )

Category 3: Applications -- Science and Engineering (Statistics )

Citation: IBM Research Report RC24303 (July, 2007)

Download: [PDF]

Entry Submitted: 07/18/2007
Entry Accepted: 07/18/2007
Entry Last Modified: 07/18/2007

Modify/Update this entry