The Cost of Troubleshooting Cost Clusters with Inside Information

Thorsten Ottosen, Finn Jensen
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:408-415, 2010.

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 \cdot lg n)$ time ($n$ being the number of actions) by the well-known ”P-over-C” algorithm due to Kadane and Simon, but an efficient 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 \cdot 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-ottosen10a, title = {The Cost of Troubleshooting Cost Clusters with Inside Information}, author = {Ottosen, Thorsten and Jensen, Finn}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {408--415}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/ottosen10a/ottosen10a.pdf}, url = {https://proceedings.mlr.press/r8/ottosen10a.html}, 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 \cdot lg n)$ time ($n$ being the number of actions) by the well-known ”P-over-C” algorithm due to Kadane and Simon, but an efficient 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 \cdot 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T The Cost of Troubleshooting Cost Clusters with Inside Information %A Thorsten Ottosen %A Finn Jensen %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-ottosen10a %I PMLR %P 408--415 %U https://proceedings.mlr.press/r8/ottosen10a.html %V R8 %X 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 \cdot lg n)$ time ($n$ being the number of actions) by the well-known ”P-over-C” algorithm due to Kadane and Simon, but an efficient 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 \cdot 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. %Z Reissued by PMLR on 04 October 2026.
APA
Ottosen, T. & Jensen, F.. (2010). The Cost of Troubleshooting Cost Clusters with Inside Information. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:408-415 Available from https://proceedings.mlr.press/r8/ottosen10a.html. Reissued by PMLR on 04 October 2026.

Related Material