| bibtype |
J -
Journal Article
|
| ARLID |
0397466 |
| utime |
20240103203114.3 |
| mtime |
20140618235959.9 |
| WOS |
000334087400005 |
| DOI |
10.1016/j.ijar.2013.07.003 |
| title
(primary) (eng) |
Decision-theoretic troubleshooting: Hardness of approximation |
| specification |
| page_count |
12 s. |
| media_type |
P |
|
| serial |
| ARLID |
cav_un_epca*0256774 |
| ISSN |
0888-613X |
| title
|
International Journal of Approximate Reasoning |
| volume_id |
55 |
| volume |
4 (2014) |
| page_num |
977-988 |
| publisher |
|
|
| keyword |
Decision-theoretic troubleshooting |
| keyword |
Hardness of approximation |
| keyword |
NP-completeness |
| author
(primary) |
| ARLID |
cav_un_auth*0272969 |
| name1 |
Lín |
| name2 |
Václav |
| full_dept (cz) |
Matematická teorie rozhodování |
| full_dept (eng) |
Department of Decision Making Theory |
| department (cz) |
MTR |
| department (eng) |
MTR |
| institution |
UTIA-B |
| full_dept |
Department of Decision Making Theory |
| fullinstit |
Ústav teorie informace a automatizace AV ČR, v. v. i. |
|
| cas_special |
| project |
| project_id |
GA13-20012S |
| agency |
GA ČR |
| ARLID |
cav_un_auth*0292670 |
|
| abstract
(eng) |
Decision-theoretic troubleshooting is one of the areas to which Bayesian networks can be applied. Given a probabilistic model of a malfunctioning man-made device, the task is to construct a repair strategy with minimal expected cost. The problem has received considerable attention over the past two decades. Efficient solution algorithms have been found for simple cases, whereas other variants have been proven NP-complete. We study several variants of the problem found in literature, and prove that computing approximate troubleshooting strategies is NP-hard. In the proofs, we exploit a close connection to set-covering problems. |
| reportyear |
2015 |
| RIV |
BB |
| inst_support |
RVO:67985556 |
| permalink |
http://hdl.handle.net/11104/0225901 |
| confidential |
S |
| mrcbT16-e |
COMPUTERSCIENCEARTIFICIALINTELLIGENCE |
| mrcbT16-j |
0.683 |
| mrcbT16-s |
1.460 |
| mrcbT16-4 |
Q1 |
| mrcbT16-B |
58.39 |
| mrcbT16-C |
81.707 |
| mrcbT16-D |
Q2 |
| mrcbT16-E |
Q1 |
| arlyear |
2014 |
| mrcbU34 |
000334087400005 WOS |
| mrcbU63 |
cav_un_epca*0256774 International Journal of Approximate Reasoning 0888-613X 1873-4731 Roč. 55 č. 4 2014 977 988 Elsevier |
|