ACO Alumni Lecture series: Algorithms for minimum norm combinatorial optimization
- ACO Student Seminar
- Friday, October 2, 2020 - 13:00 for 1 hour (actually 50 minutes)
- Dr. Deepernab Chakrabarty – CS, Dartmouth College – email@example.com
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.