An Intersection Inequality for Discrete Distributions and Related Generation Problems

Abstract

Given two finite sets of points $\mathcal{X},\mathcal{Y}$ in ℝⁿ 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 $\left| \mathcal{X} \right| \leqslant n\left| \mathcal{Y} \right|$. 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 ℝⁿ. 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.

The research of the first four authors was supported in part by the National Science Foundation Grant IIS-0118635. The research of the first and third authors was also supported in part by the Office of Naval Research Grant N00014-92-J-1375. The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science. The fifth author was supported in part by the Scientific Grant in Aid of the Ministry of Education, Science, Sports, Culture and Technology of Japan.