UBC CORDS/COCANA Operations Research Seminar: Michael Friedlander
Topic
When can you trust an optimal assignment?
Speakers
Details
Abstract: The assignment problem pairs workers with tasks at the lowest total cost. But costs are often measured,
estimated, and rounded. How much error can we tolerate? Classical sensitivity analysis furnishes an
answer, but only after the fact. We instead seek a bound a priori. Counterintuitively, randomness helps:
superpose a Gaussian perturbation and, whatever the costs, the tolerable error admits a lower bound that
depends exclusively on the problem size, the scale of the perturbation, and a preselected confidence
level. This bound informs three choices: the strength of quadratic regularization, the tolerance for the
auction algorithm, and the requisite number of bits to store the data.
Biography: My research develops mathematical foundations and algorithms for fitting models to data. This work
draws on convex analysis, duality theory, and geometry to design methods that scale to massive datasets.
Our algorithms and open-source software, including SPGL1 for sparse recovery, are used in signal
processing, geophysical imaging, machine learning, and quantum computing
Additional Information
This event is a part of the CORDS/COCANA Operations Research Seminar.
For the current seminar schedule please go to the Seminar website.