MSBE group presents a research seminar from Professor Walsh on 'Capacitated Facility Location Problems'.

Tuesday 9 July 2019
Professor Toby Walsh; Scientia Professor of Artificial Intelligence; UNSW Sydney


The facility location problem looks to find the optimal place to locate a facility (e.g. school or warehouse) to minimise the distance that agents (e.g. students or shops) are from the facility serving them. I study such problems in one dimension where each facility can serve only a limited number of agents, and consider both the optimisation and mechanism design perspectives. The addition of capacities, which have not been considered much in previous work, makes the facility location problem harder to solve. I show, for instance, that a number of mechanisms lose either 'strategyproofness' or a bound on the solution quality. I identify instead some new mechanisms that are 'strategyproof' and achieve good approximation guarantees.