Optimization Online


Nonlinear Matroid Optimization and Experimental Design

Yael Berstein(yaelber***at***tx.technion.ac.il)
Jon Lee(jonlee***at***us.ibm.com)
Hugo Maruri-Aguilar(h.maruri-aguilar***at***lse.ac.uk)
Shmuel Onn(onn***at***ie.technion.ac.il)
Eva Riccomagno(riccomagno***at***dima.unige.it)
Robert Weismantel(weismantel***at***imo.math.uni-magdeburg.de)
Henry Wynn(h.wynn***at***lse.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society