University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte Colloquium Seminar - Chaitanya SwamyExport this event to calendar

Friday, September 6, 2019 — 3:30 PM EDT

Title: Approximation Algorithms for Minimum-Norm Optimization Problems

Speaker: Chaitanya Swamy
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

In many optimization problems, a feasible solution induces a multidimensional cost vector. For example, in k-clustering, opening k facilities induces an assignment-cost vector indexed by the clients; in load-balancing, a schedule induces a load vector across the machines. Typically, one seeks a solution that either minimizes the sum of all entries, or the maximum entry of this vector, and the resulting problems (k-median, k-center, and makespan minimization) are classical NP-hard problems that have been extensively studied; given their NP-hardness, one seeks to design approximation algorithms for these problems. We consider a general optimization problem that we call minimum-norm optimization, where we are given an arbitrary monotone, symmetric norm, and we seek a solution that minimizes the norm of the induced cost vector. Monotone, symmetric norms are versatile and include L_p norms, Top-l norms (sum of the l largest coordinates in absolute value), and ordered norms (nonnegative linear combination of Top-l norms), and consequently, minimum-norm optimization models a wide variety of problems under one umbrella. 

We give a general framework for tackling minimum-norm optimization, and utilize this to obtain constant-factor approximation algorithms for  minimum-norm k-clustering and minimum-norm load balancing. These constitute the first constant-factor approximations for such a general suite of objectives. At a technical level, one of our chief insights is that minimum-norm optimization can be reduced to a special case that we call min-max ordered optimization, which highlights the fundamental role played by top-l norms. The main ingredient in solving min-max ordered optimization is a deterministic, oblivious rounding procedure for suitable LP relaxations of the load-balancing and k-clustering problems.

This is joint work with Deeparnab Chakrabarty. The talk will be self-contained.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
  1. 2021 (37)
    1. April (6)
    2. March (13)
    3. February (8)
    4. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)