Yael Berstein

Nonlinear optimization for matroid intersection and extensions

  • Yael Berstein
  • Jon Lee
  • Shmuel Onn
  • Robert Weismantel
    • Categories Combinatorial Optimization, Nonlinear Optimization Tags , ,

    We address optimization of nonlinear functions of the form $f(Wx)$~, where $f:\R^d\rightarrow \R$ is a nonlinear function, $W$ is a $d\times n$ matrix, and feasible $x$ are in some large finite set $\calF$ of integer points in $\R^n$~. Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes … Read more

    Nonlinear Matroid Optimization and Experimental Design

  • Yael Berstein
  • Jon Lee
  • Hugo Maruri-Aguilar
  • Shmuel Onn
  • Eva Riccomagno
  • Robert Weismantel
  • Henry Wynn
    • Categories Graphs and Matroids, Nonlinear Optimization, Statistics Tags , , , , ,

    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 … Read more