2 results
Search Results
Now showing 1 - 2 of 2
- ItemNonlinear matroid optimization and experimental design(Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2007) Berstein, Yael; Lee, Jon; Maruri-Aguilar, Hugo; Onn, Shmueel; Riccomagno, Eva; Weismantel, Robert; Wynn, HenryWe 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.
- ItemNonlinear optimization for matroid intersection and extensions(Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2008) Berstein, Yael; Lee, Jon; Onn, Shmuel; Weismantel, RobertWe address optimization of nonlinear functions of the form f(Wx) , where f : Rd ! R is a nonlinear function, W is a d × n matrix, and feasible x are in some large finite set F of integer points in Rn . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f , W and F . One of our main motivations is multi-objective discrete optimization, where f trades off the linear functions given by the rows of W . Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures. We assume that the convex hull of F is well-described by linear inequalities (i.e., we have an efficient separation oracle). For example, the set of characteristic vectors of common bases of a pair of matroids on a common ground set satisfies this property for F . In this setting, the problem is already known to be intractable (even for a single matroid), for general f (given by a comparison oracle), for (i) d = 1 and binary-encoded W , and for (ii) d = n and W = I . Our main results (a few technicalities suppressed): 1- When F is well described, f is convex (or even quasiconvex), and W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic algorithm for maximization. 2- When F is well described, f is a norm, and binary-encoded W is nonnegative, we give an efficient deterministic constant-approximation algorithm for maximization. 3- When F is well described, f is “ray concave” and non-decreasing, and W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic constantapproximation algorithm for minimization. 4- When F is the set of characteristic vectors of common bases of a pair of vectorial matroids on a common ground set, f is arbitrary, and W has a fixed number of rows and is unary encoded, we give an efficient randomized algorithm for optimization.