Given a set of points with weights that are not known precisely, but are known to fall within some range, considers the possible weighted centroids arising from different choices of weights in each range. The combinatorics of this problem are closely connected with those of zonotopes.
(BibTeX – Citations – CiteSeer – ACM DL)
I use Mathematica to construct zonotopes and display zonohedra. Many examples are shown, including one used for a lower bound in "The centroid of points with approximate weights". This paper is also available in HTML and Mathematica notebook formats.
We use the ellipsoid method to develop (theoretically) efficient algorithms for optimizing linear functions on intersections of zonotopes, and show how to apply this to train soft-margin support vector classifiers.
We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. Such problems can be viewed as a simple form of two-stage stochastic programming. We show that if d, the number of values in the support of the distributions, is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.
Geometry – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.