When can you trust an optimal assignment?

Fri Nov 13, 22:30-23:30 (3 days ago)

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

Export talk to