An Efficient Branch-and-Bound Solver for Hitting Set

被引：0

作者：

Blaesius, Thomas ^{[1
]}

Friedrich, Tobias ^{[2
]}

Stangl, David ^{[2
]}

Weyand, Christopher ^{[1
]}

机构：

[1] Karlsruhe Inst Technol, Karlsruhe, Germany

[2] Hasso Plattner Inst, Potsdam, Germany

来源：

2022 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX | 2022年

关键词：

APPROXIMATION ALGORITHMS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The hitting set problem asks for a collection of sets over a universe U to find a minimum subset of U that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instances from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.

引用

页码：209 / 220

页数：12

共 35 条

[1] A kernelization algorithm for d-Hitting Set [J].

Abu-Khzam, Faisal N. .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2010, 76 (07) :524-531

[2] Fast local search for the maximum independent set problem [J].

Andrade, Diogo V. ;

Resende, Mauricio G. C. ;

Werneck, Renato F. .

JOURNAL OF HEURISTICS, 2012, 18 (04) :525-547

[3]

[Anonymous], GUROBI OPTIMIZER REF, P2021

[4] Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery [J].

Birnick, Johann ;

Blaesius, Thomas ;

Friedrich, Tobias ;

Naumann, Felix ;

Papenbrock, Thorsten ;

Schirneck, Martin .

PROCEEDINGS OF THE VLDB ENDOWMENT, 2020, 13 (11) :2270-2283

[5] Understanding the Effectiveness of Data Reduction in Public Transportation Networks [J].

Blaesius, Thomas ;

Fischbeck, Philipp ;

Friedrich, Tobias ;

Schirneck, Martin .

ALGORITHMS AND MODELS FOR THE WEB GRAPH, WAW 2019, 2019, 11631 :87-101

[6]

Bocker Sebastian, 2007, P 6 AS PAC BIOINF C, DOI [10.1142/97818481610920023, DOI 10.1142/97818481610920023]

[7] Into the Square On the Complexity of Some Quadratic-time Solvable Problems [J].

Borassi, Michele ;

Crescenzi, Pierluigi ;

Habib, Michel .

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2016, 322 :51-67

[8]

Brankovic Ljiljana, 2012, Approximation and Online Algorithms. 9th International Workshop, WAOA 2011. Revised Selected Papers, P63, DOI 10.1007/978-3-642-29116-6_6

[9] Algorithms for the set covering problem [J].

Caprara, A ;

Toth, P ;

Fischetti, M .

ANNALS OF OPERATIONS RESEARCH, 2000, 98 (1-4) :353-371

[10] Finding exact hitting set solutions for systems biology applications using heterogeneous GPU clusters [J].

Carastan-Santos, Danilo ;

de Camargo, Raphael Y. ;

Martins, David C., Jr. ;

Song, Siang W. ;

Rozante, Luiz C. S. .

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2017, 67 :418-429

← 1 2 3 4 →