AI-based Optimisation Seminar Series 7th July
Speaker Professor Toby Walsh
FACILITY LOCATION
The facility location problem is a classic optimisation problem studied in AI, Operations Research and Game Theory. In this talk, I consider this problem from both an algorithmic and mechanism design perspectives. From the algorithmic perspective, I argue that locating facilities to minimise either the total travel cost to all agents or the maximum cost of any agent is NP-hard.
However, the problem is fixed-parameter tractable. The optimal solution can be computed in polynomial time whenever the number of facilities is bounded or when all facilities have identical capacities. I will also consider the problem from a mechanism design perspective where the agents are strategic and need not reveal their true locations. I consider whether we can design mechanisms that are strategy-proof and achieve approximation guarantees with respect to the optimal solution.
Toby Walsh is Professor of Artificial Intelligence at UNSW and Fellow of the Australia Academy of Science. He appears regularly on TV and radio. His most recent book is “2062: The World that AI Made”.
WED JULY 4PM – 5PM AEST
ZOOM Meeting ID: 840 4714 8969; Password: 546650