Bruce Shepherd

Abstract: Garg Vazarani and Yannakakis showed that the integrality gap for (the natural LP relaxation of) maximum disjoint paths (MEDP) in planar graphs is $\\Omega(\\sqrt{n})$. Noting that their gap example (a grid minor) all but disappears if edge...

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...

In the d-dimensional bin packing problem (VBP), one is given vectors x1, x2, …, xn in Rd and the goal is to partition them into a minimum number of "feasible" sets. A set is feasible if the sum of its vectors does not have a component exceeding 1...

We first give an accessible overview of combinatorial optimization and highlight the role of mathematics and theoretical computer science in developing efficient solution techniques. Tree structures have appeared persistently both in the models and...