In the thesis we study a number of different scenarios of planning
under uncertainty motivated by applications from robot navigation,
communication network design and other areas. We develop approximation
algorithms for several NP-hard stochastic combinatorial optimization
problems in which the input is uncertain...
The first problem we consider is motivated by a robot navigation
application. The goal is to specify 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. Another problem studied is
concerned with designing a routing network under a probabilistic
distribution of clients to be connected to a central server. Finally,
we examine stochastic versions of several classical combinatorial
optimization problems (including bin-packing, vertex cover, and
others) in the context of a recourse framework, in which one can "plan
ahead" based on limited information about the problem input, or "wait
and see" until the entire input becomes known, albeit incurring
Originally posted by Tim Allen:
Mark's answer talked about the logistics of packing airplanes, integrated chip design, etc. But I want to know what type of programmers regularly see NP-Complete problems?
Originally posted by Ellen Zhao:
So, if you are not going to pursuit a phD in computer science or you are not preparing for an exam( like me ), don't worry too much about it. Being aware of some import conclusions is enough to help you gain understanding to advanced practical algorithms.