Approximation algorithms for combinatorial optimization under uncertainty

Combinatorial optimization problems arise in many fields of industry and technology, where they are frequently used in production planning, transportation, and communication network design. Whereas in the context of classical discrete optimization it is usually assumed that the problem inputs are known, in many real-world applications some of the data may be subject to an uncertainty, often because it represents information about the future. In the field of stochastic optimization uncertain parameters are usually represented as random variables that have known probability distributions. In this thesis we study a number of different scenarios of planning under uncertainty motivated by applications from robotics, communication network design and other areas. We develop approximation algorithms for several NP-hard stochastic combinatorial optimization problems in which the input is uncertain - modeled by probability distribution - and the goal is to design a solution in advance so as to minimize expected future costs or maximize expected future profits. We develop techniques for dealing with certain probabilistic cost functions making it possible to derive combinatorial properties of an optimum solution. This enables us to make connections with already well-studied combinatorial optimization problems and apply some of the tools developed for them. The first problem we consider is motivated by an application from AI, in which a mobile robot delivers packages to various locations. The goal is to design a route for robot to follow so as to maximize the value of packages successfully delivered subject to an uncertainty in the robot's lifetime.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2003

Author dc:creator

• Minkoff, Maria, 1976-

Advisor dc:contributor.advisor

• David R. Karger.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/87452

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/87452