講   題:Polynomially computable sharp probability bounds

主 講 人:Endre Boros特聘教授

(Rutgers University,匈牙利國家科學院院士)

主 持 人:林義貴 講座教授

主辦單位:交通大學工業工程與管理學系

時間: 108年11月7日(星期四)13:20~15:00

地   點:管二館 MB418 室

演講摘要:

We consider the problem of finding upper and lower bounds for the probability of the union of events when the probabilities of the single events and the probabilities of the intersections of up to m events are given. It is known that the best possible bounds can be obtained by solving linear programming problems with a number of variables that is exponential in the number of events. Because of their size and structure, these large linear programs are known to be very hard to solve. In the literature simpler, polynomially sized aggregations are considered and numerous closed form or polynomially computable bounds are derived from those. We present here a new approach that introduces additional constraints to the dual linear programming problems in such a way that those become polynomially solvable. By using different sets of additional constraints, we introduce three new classes of polynomially computable upper and lower bounds. We show that they dominate almost all efficiently computable bounds known in the literature. Furthermore, by characterizing the vertices of two new classes of polyhedra, we can show that in two cases our bounds coincide with classical bounds, proving new extremal properties for those well-known bounds. Finally, we provide extensive numerical results comparing the average tightness of the various bounds on a large number of instances.

演講性質:學術研究專題

歡迎聽講