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)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

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.

Originalsprache	englisch
Titel	ECAI 2012 - 20th European Conference on Artificial Intelligence
Untertitel	27–31 August 2012, Montpellier, France – Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track
Redakteure/-innen	Luc de Raedt
Erscheinungsort	Amsterdam
Herausgeber (Verlag)	IOS Press
Seiten	648-653
ISBN (Print)	978-1-61499-097-0
DOIs	https://doi.org/10.3233/978-1-61499-098-7-648
Publikationsstatus	Veröffentlicht - 2012
Veranstaltung	20th European Conference on Artificial Intelligence: ECAI 2012 - Montpellier, Frankreich Dauer: 27 Aug. 2012 → 31 Aug. 2012

Publikationsreihe

Name	Frontiers in Artificial Intelligence and Applications
Herausgeber (Verlag)	IOS Press
Band	242

Konferenz

Konferenz	20th European Conference on Artificial Intelligence
Land/Gebiet	Frankreich
Ort	Montpellier
Zeitraum	27/08/12 → 31/08/12

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

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

FWF - MoDiaForTeD - Modellbasierte Diagnose für Formale Temporale Beschreibungen
Quaritsch, S. (Teilnehmer (Co-Investigator)) & Pill, I. H. (Projektleiter (Principal Investigator))
1/11/10 → 30/06/15
Projekt: Forschungsprojekt
Artificial Intelligence & Applications
Pill, I. H. (Teilnehmer (Co-Investigator)), Wotawa, F. (Teilnehmer (Co-Investigator)) & Haase, V. (Teilnehmer (Co-Investigator))
16/11/00 → 31/12/24
Projekt: Arbeitsgebiet

Dieses zitieren

Pill, I. H., & Quaritsch, T. (2012). Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. in L. D. Raedt (Hrsg.), 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 (S. 648-653). (Frontiers in Artificial Intelligence and Applications; Band 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. Hrsg. / Luc de Raedt. Amsterdam: IOS Press, 2012. S. 648-653 (Frontiers in Artificial Intelligence and Applications; Band 242).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Pill, IH & Quaritsch, T 2012, Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. in LD Raedt (Hrsg.), 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, Bd. 242, IOS Press, Amsterdam, S. 648-653, 20th European Conference on Artificial Intelligence, Montpellier, Frankreich, 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, Hrsg., 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. S. 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. Hrsg. / Luc de Raedt. Amsterdam : IOS Press, 2012. S. 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

Publikationsreihe

Konferenz

Fields of Expertise

Zugriff auf Dokument

Fingerprint

Projekte

FWF - MoDiaForTeD - Modellbasierte Diagnose für Formale Temporale Beschreibungen

Artificial Intelligence & Applications

Dieses zitieren