hide
Free keywords:
-
Abstract:
Given two finite sets of points \mathcal X},{\mathcal Y} in
{\mathbb{R}}^n which can be separated by a nonnegative linear function, and
such that the componentwise minimum of any two distinct points in {\mathcal
X} is dominated by some point in {\mathcal Y}, we show that
\vert{\mathcal X}\vert≤q n\vert{\mathcal Y}\vert. As a consequence of this
result, we obtain quasi-polynomial time algorithms for generating all maximal
integer feasible solutions for a given monotone system of separable
inequalities, for generating all p-inefficient points of a given discrete
probability distribution, and for generating all maximal empty hyper-rectangles
for a given set of points in {\mathbb{R}^n. This provides a substantial
improvement over previously known exponential algorithms for these generation
problems related to Integer and Stochastic Programming, and Data Mining.
Furthermore, we give an incremental polynomial time generation algorithm for
monotone systems with fixed number of separable inequalities, which, for the
very special case of one inequality, implies that for discrete probability
distributions with independent coordinates, both p-efficient and p-inefficient
points can be separately generated in incremental polynomial time.
