Approximation and Online Algorithms

In many situations, it is impossible to obtain exact algorithms for optimization problems, because of limitations in computational resources, or other reasons such as information theoretic restrictions. The fields of approximation and online algorithms aim to obtain approximately optimal solutions in these scenarios. Research at Duke has made important contributions to multiple subareas in this domain, including scheduling and resource allocation, stochastic decision making, mathematical programming, and other areas of combinatorial optimization.