Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142052 | Operations Research Letters | 2016 | 5 Pages |
Abstract
We formulate a linear program whose optimal objective function value can be used in other formulations to yield improved upper and lower bounds on the probability of the union of events if we know some empty intersections of small numbers of events. The LP relaxation of an extension of the maximum independent set problem provides an upper bound on the largest number of events that have a nonempty intersection. We present numerical experiments demonstrating the effectiveness of our formulation.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kunikazu Yoda, András Prékopa,