Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Monte-Carlo optimizations for resource allocation problems in stochastic network systems
Milos Hauskrecht, Tomas Singliar
Abstract:
Real-world distributed systems and networks are often unreliable and subject to random failures of its components. Such a stochastic behavior affects adversely the complexity of optimization tasks performed routinely upon such systems, in particular, various resource allocation tasks. In this work we investigate and develop Monte Carlo solutions for a class of two-stage optimization problems in stochastic networks in which the expected value of resource allocations before and after stochastic failures needs to be optimized. The limitation of these problems is that their exact solutions are exponential in the number of unreliable network components: thus, exact methods do not scale-up well to large networks often seen in practice. We first prove that Monte Carlo optimization methods can overcome the exponential bottleneck of exact methods. Next we support our theoretical findings on resource allocation experiments and show a very good scale-up potential of the new methods to large stochastic networks
Keywords:
Pages: 305-312
PS Link:
PDF Link: /papers/03/p305-hauskrecht.pdf
BibTex:
@INPROCEEDINGS{Hauskrecht03,
AUTHOR = "Milos Hauskrecht and Tomas Singliar",
TITLE = "Monte-Carlo optimizations for resource allocation problems in stochastic network systems",
BOOKTITLE = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "305--312"
}


hosted by DSL   •   site info   •   help