Discrete Math Seminar: Bruce Sheperd

Robust optimization is a paradigm for dealing with optimization problems whose input is uncertain. For instance, consider building a system (bridge, network, etc.) whose future demand (or stress) is unknown but bounded. Say we know that the set of possible demands will come from a given convex region called the "universe". A solution/design is called robust if it supports any demand from the universe. Robust optimization asks for a minimum cost robust solution. We consider this model for the design of communication (data) networks where future demand can be both unknown and varying over time. We will discuss in detail one variant of robust network design known as the Virtual Private Network (VPN) problem. We will also mention several open (theoretical and practical) questions.