TY - JOUR
T1 - Reliable assignments of processors to tasks and factoring on matroids
AU - Colbourn, Charles J.
AU - Elmallah, Ehab S.
N1 - Funding Information:
Correspondence to: Charles J. Colbourn, Waterloo, Waterloo, Ont., Canada N2L 3Gl. * Research supported by NSERC Canada
PY - 1993/4/28
Y1 - 1993/4/28
N2 - In the simple assignment problem, there are n processors, m tasks, and a relation between the processors and tasks; this relation indicates the ability of the processor to perform the task. When the processors fail independently with known probabilities, two performance issues arise. First, with what probability can the operating processors all be kept busy? Second, with what probability can the operating processors perform the same number of tasks that all processors could? We formulate these questions on the underlying transversal matroid. We first prove that counting minimum cardinality circuits in this matroid is # P-complete and, hence, that both questions are also # P-complete. Secondly, we devise a factoring algorithm with series and parallel reductions to compute the exact solutions of the above problems. We then outline some efficient strategies for bounding the probabilities.
AB - In the simple assignment problem, there are n processors, m tasks, and a relation between the processors and tasks; this relation indicates the ability of the processor to perform the task. When the processors fail independently with known probabilities, two performance issues arise. First, with what probability can the operating processors all be kept busy? Second, with what probability can the operating processors perform the same number of tasks that all processors could? We formulate these questions on the underlying transversal matroid. We first prove that counting minimum cardinality circuits in this matroid is # P-complete and, hence, that both questions are also # P-complete. Secondly, we devise a factoring algorithm with series and parallel reductions to compute the exact solutions of the above problems. We then outline some efficient strategies for bounding the probabilities.
UR - http://www.scopus.com/inward/record.url?scp=38249003677&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249003677&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(93)90360-6
DO - 10.1016/0012-365X(93)90360-6
M3 - Article
AN - SCOPUS:38249003677
SN - 0012-365X
VL - 114
SP - 115
EP - 129
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -