Optimizing Link Assignment to Enhance Service in Probabilistic Network

Free registration required

Executive Summary

In this paper, the authors make minor adaptations to the well-known notion of probabilistic network from the machine learning community and use it as their communication model. They then formally define the above optimization problem as the Link Assignment for Successful Service problem (LASS). While LASS can be reduced to the maximum matching problem in the deterministic case (where the success probabilities of each edge is 1), they show that in the probabilistic case it is NP-hard (and MaxSNP-hard). An equivalent integer programming formulation for LASS is obtained so that for small input size, the problem may be efficiently solved by the standard IP solver in practice. To tackle large input size, various heuristics are designed.

  • Format: PDF
  • Size: 403.3 KB