Euler Polytopes and Convex Matroid Optimization

Del Pia and Michini recently improved the upper bound of kd due to Kleinschmidt and Onn for the largest possible diameter of the convex hull of a set of points in dimension d whose coordinates are integers between 0 and k. We introduce Euler polytopes which include a family of lattice polytopes with diameter (k+1)d/2, … Read more

Intractability of approximate multi-dimensional nonlinear optimization on independence systems

We consider optimization of nonlinear objective functions that balance $d$ linear criteria over $n$-element independence systems presented by linear-optimization oracles. For $d=1$, we have previously shown that an $r$-best approximate solution can be found in polynomial time. Here, using an extended Erdos-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a $\rho n$-best solution … Read more

Nonlinear optimization for matroid intersection and extensions

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 Optimization over a Weighted Independence System

We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual … Read more

On Test Sets for Nonlinear Integer Maximization

A finite test set for an integer maximization problem enables us to verify whether a feasible point attains the global maximum. We establish in this paper several general results that apply to integer maximization problems with nonlinear objective functions. Citation Operations Research Letters 36 (2008) 439–443 Article Download View On Test Sets for Nonlinear Integer … Read more

Nonlinear Matroid Optimization and Experimental Design

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

Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution. In the first part of this paper, we construct new … Read more

Accuracy Certificates for Computational Problems with Convex Structure

The goal of the current paper is to introduce the notion of certificates which verify the accuracy of solutions of computational problems with convex structure; such problems include minimizing convex functions, variational inequalities corresponding to monotone operators, computing saddle points of convex-concave functions and solving convex Nash equilibrium problems. We demonstrate how the implementation of … Read more