Starting from the work of Bonferroni more than one century ago, several methods have been proposed in the literature for the problem of finding upper bounds for the probability of the union of n events when the individual probabilities of the events as well as the probabilities of all intersections of k-tuples of these events are known. The most popular methods for obtaining bounds are based either on a linear programming formulation of the problem or on graph techniques. Some of the graph-based bounds are based on a greedy algorithm and can be found in polynomial time. For most other graph-based bounds proposed in the literature, only heuristic algorithms have been provided to find the best bound with no attempt to solve the problem exactly or to determine its computational complexity. Here we show that the problems of finding the best graph bounds based on cherry trees or on chordal graphs are both NP-complete. Furthermore, we propose a heuristic method to efficiently find a good upper bound based on the chordal graph approach.

Complexity of some graph-based bounds on the probability of a union of events / Scozzari, Andrea; Tardella, Fabio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 244(2018), pp. 186-197. [10.1016/j.dam.2018.03.012]

Complexity of some graph-based bounds on the probability of a union of events

Tardella, Fabio
2018

Abstract

Starting from the work of Bonferroni more than one century ago, several methods have been proposed in the literature for the problem of finding upper bounds for the probability of the union of n events when the individual probabilities of the events as well as the probabilities of all intersections of k-tuples of these events are known. The most popular methods for obtaining bounds are based either on a linear programming formulation of the problem or on graph techniques. Some of the graph-based bounds are based on a greedy algorithm and can be found in polynomial time. For most other graph-based bounds proposed in the literature, only heuristic algorithms have been provided to find the best bound with no attempt to solve the problem exactly or to determine its computational complexity. Here we show that the problems of finding the best graph bounds based on cherry trees or on chordal graphs are both NP-complete. Furthermore, we propose a heuristic method to efficiently find a good upper bound based on the chordal graph approach.
File allegati a questo prodotto
File Dimensione Formato  
Tardella_Complexity-graph-based-bounds_2018.pdf

solo gestori archivio

Note: Link editore: https://www.sciencedirect.com/science/article/pii/S0166218X18301033?via%3Dihub
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 712.38 kB
Formato Adobe PDF
712.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/1185743
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact