Search Results

Documents authored by Mannila, Heikki

Document
DOI: 10.4230/LIPIcs.ESA.2026.129
Optimal Union Probability Interval Is NP-Hard

Authors: Petteri Kaski, Heikki Mannila, and Chandra Kanta Mohapatra

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
A problem dating back to Boole [Laws of Thought, Walton & Maberly, 1854] is what can be computed about the probability of a finite union of events when given as input the probabilities of intersections of some of the events. The modern geometric study of the problem can be traced back to Hailperin [Amer. Math. Monthly 2 (1965) 343-359] who phrased the problem in the language of linear programming and generalized it to logical formulas of the events other than disjunction, heralding a substantial body of work in probabilistic logic [Nilsson, Artif. Intell. 28 (1986) 71-87], including the probabilistic satisfiability problem of Georgakopoulos, Kavvadis, and Papadimitriou [J. Complexity 4 (1988) 1-11], as well as fundamental connections to the geometry of metrics via cut and correlation polytopes [Deza and Laurent, Geometry of Cuts and Metrics, Springer, 1997] and to the study of marginal polytopes in graphical models of machine learning [Wainwright and Jordan, Found. Trends Mach. Learn. 1 (2008) 1-305]. This paper (i) describes the pertinent geometry of Boole’s problem via coordinate projections of an elementary polytope arising essentially from Hailperin’s linear program on the atoms of a Venn diagram, and (ii) shows that computing the optimal interval for the union probability is NP-hard, resolving an apparent gap in the literature highlighted by Pitowsky [Math. Programming 50 (1991) 395-414] and Boros et al. [Math. Oper. Res. 39 (2014) 1311-1329 and 51 (2026) 134-148].
Cite as

Petteri Kaski, Heikki Mannila, and Chandra Kanta Mohapatra. Optimal Union Probability Interval Is NP-Hard. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 129:1-129:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaski_et_al:LIPIcs.ESA.2026.129,
  author =	{Kaski, Petteri and Mannila, Heikki and Mohapatra, Chandra Kanta},
  title =	{{Optimal Union Probability Interval Is NP-Hard}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{129:1--129:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.129},
  URN =		{urn:nbn:de:0030-drops-272650},
  doi =		{10.4230/LIPIcs.ESA.2026.129},
  annote =	{Keywords: combinatorial probability, computational complexity, correlation polytope, generalized Bonferroni inequalities, graphical models, inclusion-exclusion, intersection probability, linear programming, union polytope}
}
Document
DOI: 10.4230/DagSemProc.04292.1
Data Mining: The Next Generation

Authors: Raghu Ramakrishnan, Rakesh Agrawal, Johann-Christoph Freytag, Toni Bollinger, Christopher W. Clifton, Saso Dzeroski, Jochen Hipp, Daniel Keim, Stefan Kramer, Hans-Peter Kriegel, Ulf Leser, Bing Liu, Heikki Mannila, Rosa Meo, Shinichi Morishita, Raymond Ng, Jian Pei, Prabhakar Raghavan, Myra Spiliopoulou, Jaideep Srivastava, and Vicenc Torra

Published in: Dagstuhl Seminar Proceedings, Volume 4292, Perspectives Workshop: Data Mining: The Next Generation (2005)

Abstract
Data Mining (DM) has enjoyed great popularity in recent years, with advances in both research and commercialization. The first generation of DM research and development has yielded several commercially available systems, both stand-alone and integrated with database systems; produced scalable versions of algorithms for many classical DM problems; and introduced novel pattern discovery problems. In recent years, research has tended to be fragmented into several distinct pockets without a comprehensive framework. Researchers have continued to work largely within the parameters of their parent disciplines, building upon existing and distinct research methodologies. Even when they address a common problem (for example, how to cluster a dataset) they apply different techniques, different perspectives on what the important issues are, and different evaluation criteria. While different approaches can be complementary, and such a diversity is ultimately a strength of the field, better communication across disciplines is required if DM is to forge a distinct identity with a core set of principles, perspectives, and challenges that differentiate it from each of the parent disciplines. Further, while the amount and complexity of data continues to grow rapidly, and the task of distilling useful insight continues to be central, serious concerns have emerged about social implications of DM. Addressing these concerns will require advances in our theoretical understanding of the principles that underlie DM algorithms, as well as an integrated approach to security and privacy in all phases of data management and analysis. Researchers from a variety of backgrounds assembled at Dagstuhl to re-assess the current directions of the field, to identify critical problems that require attention, and to discuss ways to increase the flow of ideas across the different disciplines that DM has brought together. The workshop did not seek to draw up an agenda for the field of DM. Rather, it offers the participants’ perspective on two technical directions – compositionality and privacy – and describes some important application challenges that drove the discussion. Both of these directions illustrate the opportunities for crossdisciplinary research, and there was broad agreement that they represent important and timely areas for further work; of course, the choice of these directions as topics for discussion also reflects the personal interests and biases of the workshop participants.
Cite as

Raghu Ramakrishnan, Rakesh Agrawal, Johann-Christoph Freytag, Toni Bollinger, Christopher W. Clifton, Saso Dzeroski, Jochen Hipp, Daniel Keim, Stefan Kramer, Hans-Peter Kriegel, Ulf Leser, Bing Liu, Heikki Mannila, Rosa Meo, Shinichi Morishita, Raymond Ng, Jian Pei, Prabhakar Raghavan, Myra Spiliopoulou, Jaideep Srivastava, and Vicenc Torra. Data Mining: The Next Generation. In Perspectives Workshop: Data Mining: The Next Generation. Dagstuhl Seminar Proceedings, Volume 4292, pp. 1-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{ramakrishnan_et_al:DagSemProc.04292.1,
  author =	{Ramakrishnan, Raghu and Agrawal, Rakesh and Freytag, Johann-Christoph and Bollinger, Toni and Clifton, Christopher W. and Dzeroski, Saso and Hipp, Jochen and Keim, Daniel and Kramer, Stefan and Kriegel, Hans-Peter and Leser, Ulf and Liu, Bing and Mannila, Heikki and Meo, Rosa and Morishita, Shinichi and Ng, Raymond and Pei, Jian and Raghavan, Prabhakar and Spiliopoulou, Myra and Srivastava, Jaideep and Torra, Vicenc},
  title =	{{Data Mining: The Next Generation}},
  booktitle =	{Perspectives Workshop: Data Mining: The Next Generation},
  pages =	{1--33},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4292},
  editor =	{Rakesh Agrawal and Johann Christoph Freytag and Raghu Ramakrishnan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04292.1},
  URN =		{urn:nbn:de:0030-drops-2709},
  doi =		{10.4230/DagSemProc.04292.1},
  annote =	{Keywords: Data mining, databases, artificial intelligence, machine learning, statistics, semantics}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact