The Cost of Troubleshooting Cost Clusters with Inside Information

Thorsten Jørgen Ottosen, Finn V. Jensen

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

6 Citations (Scopus)

Abstract

Decision theoretical troubleshooting is about
minimizing the expected cost of solving a
certain problem like repairing a complicated
man-made device. In this paper we consider
situations where you have to take apart some
of the device to get access to certain clusters
and actions. Specifically, we investigate
troubleshooting with independent actions in
a tree of clusters where actions inside a cluster
cannot be performed before the cluster is
opened. The problem is non-trivial because
there is a cost associated with opening and
closing a cluster. Troubleshooting with independent
actions and no clusters can be solved
in O(n lg n) time (n being the number of
actions) by the well-known "P-over-C" algorithm
due to Kadane and Simon, but an ef-
ficient and optimal algorithm for a tree cluster
model has not yet been found. In this
paper we describe a "bottom-up P-over-C"
O(n lg n) time algorithm and show that it is
optimal when the clusters do not need to be
closed to test whether the actions solved the
problem.
Original languageEnglish
Title of host publicationProceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010)
PublisherAssociation for Uncertainty in Artificial Intelligence
Publication date2010
ISBN (Print)978-0-9749039-6-5
Publication statusPublished - 2010
Event26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) - Catalina Island, United States
Duration: 8 Jul 201011 Jul 2010

Conference

Conference26th Conference on Uncertainty in Artificial Intelligence (UAI 2010)
CountryUnited States
CityCatalina Island
Period08/07/201011/07/2010

Fingerprint

Costs

Keywords

  • Decision Theoretic Troubleshooting

Cite this

Ottosen, T. J., & Jensen, F. V. (2010). The Cost of Troubleshooting Cost Clusters with Inside Information. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) Association for Uncertainty in Artificial Intelligence.
Ottosen, Thorsten Jørgen ; Jensen, Finn V. / The Cost of Troubleshooting Cost Clusters with Inside Information. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010). Association for Uncertainty in Artificial Intelligence, 2010.
@inproceedings{ac0e7fcf8780427e83bf32eed0068620,
title = "The Cost of Troubleshooting Cost Clusters with Inside Information",
abstract = "Decision theoretical troubleshooting is about minimizing the expected cost of solving a certain problem like repairing a complicated man-made device. In this paper we consider situations where you have to take apart some of the device to get access to certain clusters and actions. Specifically, we investigate troubleshooting with independent actions in a tree of clusters where actions inside a cluster cannot be performed before the cluster is opened. The problem is non-trivial because there is a cost associated with opening and closing a cluster. Troubleshooting with independent actions and no clusters can be solved in O(n lg n) time (n being the number of actions) by the well-known {"}P-over-C{"} algorithm due to Kadane and Simon, but an ef- ficient and optimal algorithm for a tree cluster model has not yet been found. In this paper we describe a {"}bottom-up P-over-C{"} O(n lg n) time algorithm and show that it is optimal when the clusters do not need to be closed to test whether the actions solved the problem.",
keywords = "Decision Theoretic Troubleshooting",
author = "Ottosen, {Thorsten J{\o}rgen} and Jensen, {Finn V.}",
note = "Association for Uncertainty in Artificial Intelligence, AUAI",
year = "2010",
language = "English",
isbn = "978-0-9749039-6-5",
booktitle = "Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010)",
publisher = "Association for Uncertainty in Artificial Intelligence",

}

Ottosen, TJ & Jensen, FV 2010, The Cost of Troubleshooting Cost Clusters with Inside Information. in Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010). Association for Uncertainty in Artificial Intelligence, Catalina Island, United States, 08/07/2010.

The Cost of Troubleshooting Cost Clusters with Inside Information. / Ottosen, Thorsten Jørgen; Jensen, Finn V.

Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010). Association for Uncertainty in Artificial Intelligence, 2010.

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - The Cost of Troubleshooting Cost Clusters with Inside Information

AU - Ottosen, Thorsten Jørgen

AU - Jensen, Finn V.

N1 - Association for Uncertainty in Artificial Intelligence, AUAI

PY - 2010

Y1 - 2010

N2 - Decision theoretical troubleshooting is about minimizing the expected cost of solving a certain problem like repairing a complicated man-made device. In this paper we consider situations where you have to take apart some of the device to get access to certain clusters and actions. Specifically, we investigate troubleshooting with independent actions in a tree of clusters where actions inside a cluster cannot be performed before the cluster is opened. The problem is non-trivial because there is a cost associated with opening and closing a cluster. Troubleshooting with independent actions and no clusters can be solved in O(n lg n) time (n being the number of actions) by the well-known "P-over-C" algorithm due to Kadane and Simon, but an ef- ficient and optimal algorithm for a tree cluster model has not yet been found. In this paper we describe a "bottom-up P-over-C" O(n lg n) time algorithm and show that it is optimal when the clusters do not need to be closed to test whether the actions solved the problem.

AB - Decision theoretical troubleshooting is about minimizing the expected cost of solving a certain problem like repairing a complicated man-made device. In this paper we consider situations where you have to take apart some of the device to get access to certain clusters and actions. Specifically, we investigate troubleshooting with independent actions in a tree of clusters where actions inside a cluster cannot be performed before the cluster is opened. The problem is non-trivial because there is a cost associated with opening and closing a cluster. Troubleshooting with independent actions and no clusters can be solved in O(n lg n) time (n being the number of actions) by the well-known "P-over-C" algorithm due to Kadane and Simon, but an ef- ficient and optimal algorithm for a tree cluster model has not yet been found. In this paper we describe a "bottom-up P-over-C" O(n lg n) time algorithm and show that it is optimal when the clusters do not need to be closed to test whether the actions solved the problem.

KW - Decision Theoretic Troubleshooting

M3 - Article in proceeding

SN - 978-0-9749039-6-5

BT - Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010)

PB - Association for Uncertainty in Artificial Intelligence

ER -

Ottosen TJ, Jensen FV. The Cost of Troubleshooting Cost Clusters with Inside Information. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010). Association for Uncertainty in Artificial Intelligence. 2010