Optimizations for the Boolean Approach to Computing Minimal Hitting Sets

Ingo Hans Pill; Thomas Quaritsch

doi:10.3233/978-1-61499-098-7-648

Optimizations for the Boolean Approach to Computing Minimal Hitting Sets

Ingo Hans Pill, Thomas Quaritsch

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

The Boolean approach to computing minimal hitting sets proposed by Lin and Jiang is known to offer very attractive general performance, but also has its issues, specifically with a cardinality-restricted search. In this paper we propose optimizations regarding the refinement rules, also offering a revised decision strategy as well as optimized termination criteria that exploit cardinality bounds. Our experiments including artificial and real-world samples for the bounded and unbounded case show the potential of our work, where we could achieve speed-ups of up to two orders of magnitude.

Original language	English
Title of host publication	ECAI 2012 - 20th European Conference on Artificial Intelligence
Subtitle of host publication	27–31 August 2012, Montpellier, France – Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track
Editors	Luc de Raedt
Place of Publication	Amsterdam
Publisher	IOS Press
Pages	648-653
ISBN (Print)	978-1-61499-097-0
DOIs	https://doi.org/10.3233/978-1-61499-098-7-648
Publication status	Published - 2012
Event	20th European Conference on Artificial Intelligence: ECAI 2012 - Montpellier, France Duration: 27 Aug 2012 → 31 Aug 2012

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Publisher	IOS Press
Volume	242

Conference

Conference	20th European Conference on Artificial Intelligence
Country/Territory	France
City	Montpellier
Period	27/08/12 → 31/08/12

Fields of Expertise

Information, Communication & Computing

Access to Document

10.3233/978-1-61499-098-7-648Licence: CC BY-NC 3.0

FWF - MoDiaForTeD - Model-based Diagnosis for Formal Temporal Descriptions
Quaritsch, S. (Co-Investigator (CoI)) & Pill, I. H. (Principal Investigator (PI))
1/11/10 → 30/06/15
Project: Research project
Artificial Intelligence & Applications
Pill, I. H. (Co-Investigator (CoI)), Wotawa, F. (Co-Investigator (CoI)) & Haase, V. (Co-Investigator (CoI))
16/11/00 → 31/12/24
Project: Research area

Cite this

Pill, I. H., & Quaritsch, T. (2012). Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. In L. D. Raedt (Ed.), ECAI 2012 - 20th European Conference on Artificial Intelligence: 27–31 August 2012, Montpellier, France – Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track (pp. 648-653). (Frontiers in Artificial Intelligence and Applications; Vol. 242). IOS Press. https://doi.org/10.3233/978-1-61499-098-7-648

Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. / Pill, Ingo Hans; Quaritsch, Thomas.
ECAI 2012 - 20th European Conference on Artificial Intelligence: 27–31 August 2012, Montpellier, France – Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track. ed. / Luc de Raedt. Amsterdam: IOS Press, 2012. p. 648-653 (Frontiers in Artificial Intelligence and Applications; Vol. 242).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Pill, IH & Quaritsch, T 2012, Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. in LD Raedt (ed.), ECAI 2012 - 20th European Conference on Artificial Intelligence: 27–31 August 2012, Montpellier, France – Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track. Frontiers in Artificial Intelligence and Applications, vol. 242, IOS Press, Amsterdam, pp. 648-653, 20th European Conference on Artificial Intelligence, Montpellier, France, 27/08/12. https://doi.org/10.3233/978-1-61499-098-7-648

Pill IH, Quaritsch T. Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. In Raedt LD, editor, ECAI 2012 - 20th European Conference on Artificial Intelligence: 27–31 August 2012, Montpellier, France – Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track. Amsterdam: IOS Press. 2012. p. 648-653. (Frontiers in Artificial Intelligence and Applications). doi: 10.3233/978-1-61499-098-7-648

Pill, Ingo Hans ; Quaritsch, Thomas. / Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. ECAI 2012 - 20th European Conference on Artificial Intelligence: 27–31 August 2012, Montpellier, France – Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track. editor / Luc de Raedt. Amsterdam : IOS Press, 2012. pp. 648-653 (Frontiers in Artificial Intelligence and Applications).

@inproceedings{79f7344ba6d6492c8765d263c171d775,

title = "Optimizations for the Boolean Approach to Computing Minimal Hitting Sets",

abstract = "The Boolean approach to computing minimal hitting sets proposed by Lin and Jiang is known to offer very attractive general performance, but also has its issues, specifically with a cardinality-restricted search. In this paper we propose optimizations regarding the refinement rules, also offering a revised decision strategy as well as optimized termination criteria that exploit cardinality bounds. Our experiments including artificial and real-world samples for the bounded and unbounded case show the potential of our work, where we could achieve speed-ups of up to two orders of magnitude.",

author = "Pill, {Ingo Hans} and Thomas Quaritsch",

year = "2012",

doi = "10.3233/978-1-61499-098-7-648",

language = "English",

isbn = "978-1-61499-097-0",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "648--653",

editor = "Raedt, {Luc de}",

booktitle = "ECAI 2012 - 20th European Conference on Artificial Intelligence",

address = "Netherlands",

note = "20th European Conference on Artificial Intelligence : ECAI 2012 ; Conference date: 27-08-2012 Through 31-08-2012",

}

TY - GEN

T1 - Optimizations for the Boolean Approach to Computing Minimal Hitting Sets

AU - Pill, Ingo Hans

AU - Quaritsch, Thomas

PY - 2012

Y1 - 2012

N2 - The Boolean approach to computing minimal hitting sets proposed by Lin and Jiang is known to offer very attractive general performance, but also has its issues, specifically with a cardinality-restricted search. In this paper we propose optimizations regarding the refinement rules, also offering a revised decision strategy as well as optimized termination criteria that exploit cardinality bounds. Our experiments including artificial and real-world samples for the bounded and unbounded case show the potential of our work, where we could achieve speed-ups of up to two orders of magnitude.

AB - The Boolean approach to computing minimal hitting sets proposed by Lin and Jiang is known to offer very attractive general performance, but also has its issues, specifically with a cardinality-restricted search. In this paper we propose optimizations regarding the refinement rules, also offering a revised decision strategy as well as optimized termination criteria that exploit cardinality bounds. Our experiments including artificial and real-world samples for the bounded and unbounded case show the potential of our work, where we could achieve speed-ups of up to two orders of magnitude.

U2 - 10.3233/978-1-61499-098-7-648

DO - 10.3233/978-1-61499-098-7-648

M3 - Conference paper

SN - 978-1-61499-097-0

T3 - Frontiers in Artificial Intelligence and Applications

SP - 648

EP - 653

BT - ECAI 2012 - 20th European Conference on Artificial Intelligence

A2 - Raedt, Luc de

PB - IOS Press

CY - Amsterdam

T2 - 20th European Conference on Artificial Intelligence

Y2 - 27 August 2012 through 31 August 2012

ER -

Optimizations for the Boolean Approach to Computing Minimal Hitting Sets

Abstract

Publication series

Conference

Fields of Expertise

Access to Document

Projects

FWF - MoDiaForTeD - Model-based Diagnosis for Formal Temporal Descriptions

Artificial Intelligence & Applications

Cite this