Robert Hildebrand We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial xTQx+ cTx+ γ over the integer points of a bounded rational polyhedron Ax ≤b. For n variables and m inequalities, the running time is 2O(n log(n+1))(m+ 1)O(n)φ_{A,Q}^O(n)(1 + φ)O(1), where φ_{A,Q} is one plus the maximum binary encoding length of an entry of … Read more
We consider the exact minimization of a rational cubic polynomial over the integer points of a rational polytope in fixed dimension. Del Pia, Hildebrand, Weismantel, and Zemmer proved polynomial-time solvability in dimension two, while quartic polynomial minimization is already NP-hard in dimension two. We show that the bounded cubic result extends to every fixed dimension. … Read more
We study optimization methods applied to minimizing forces for poses and movements of chained Stewart platforms (SPs) that we call an “Assembler” Robot. These chained SPs are parallel mechanisms that are stronger, stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. Linking these units in … Read more
We study continuous, equality knapsack problems with uniform separable, non-convex objective functions that are continuous, strictly increasing, antisymmetric about a point, and have concave and convex regions. For example, this model captures a simple allocation problem with the goal of optimizing an expected value where the objective is a sum of cumulative distribution functions of … Read more