The Application of Novel Technology in Cultural Heritage Graph Theory, Combinatorics and Algorithms The Application of Novel Technology in Cultural Heritage Graph Theory, Combinatorics and Algorithms ???? The Application of Novel Technology in Cultural Heritage Graph Theory, Combinatorics and Algorithms

 

Approximation Algorithms for Stochastic Combinatorial and Geometric Optimization Problems


Jian Li

 

Abstract

 

The world is full of uncertainty and very often decisions have to be made way before the uncertainty is resolved. Stochastic optimization studies optimization problems with uncertain inputs or parameters, in which the uncertainty is modeled using probability theory. The area was initiated by Danzig in 1950s and has been subject to extensive research in many disciplines including computer science, math, operation research, economics, management science and social science. In this talk, I will talk about some of my recent efforts on stochastic geometric and combinatorial optimization problems. In particular, I will talk about some new results on the stochastic models for several fundamental geometric and combinatorial problems, such as minimum spanning tree, closest pair, minimum enclosing ball, shortest path and knapsack.