ACO Alumni Lecture series: Algorithms for minimum norm combinatorial optimization

ACO Student Seminar
Friday, October 2, 2020 - 1:00pm for 1 hour (actually 50 minutes)
Dr. Deepernab Chakrabarty – CS, Dartmouth College – deeparnab.chakrabarty@dartmouth.edu
He Guo

In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In k-clustering, opening k facilities induces an assignment cost vector across the clients. In this paper we consider the following minimum norm optimization problem : given an arbitrary monotone, symmetric norm, find a solution which minimizes the norm of the induced cost-vector. This generalizes many fundamental NP-hard problems. We give a general framework to tackle the minimum norm problem, and illustrate its efficacy in load balancing and, time permitting, in the clustering setting.