When can you trust an optimal assignment?
Michael Friedlander (*Friday*) (UBC Vancouver)
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.
Mathematics
Audience: researchers in the topic
PIMS-CORDS SFU Operations Research Seminar
| Organizer: | Tamon Stephen* |
| *contact for this listing |
