- Series
- ACO Alumni Lecture
- Time
- Friday, October 2, 2020 - 1:05pm for 1 hour (actually 50 minutes)
- Location
- Bluejeans link: https://bluejeans.com/264244877/0166
- Speaker
- Deeparnab Chakrabarty – Dartmouth College, NH – deeparnab@gmail.com
- Organizer
- Prasad Tetali
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.
(The speaker is an ACO alum; after the lecture, the speaker will engage with the ACO students for 30-45 minutes.)