BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//128.220.13.64//NONSGML kigkonsult.se iCalcreator 2.20//
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Johns Hopkins Algorithms and Complexity
X-WR-CALDESC:
X-FROM-URL:https://www.cs.jhu.edu/~mdinitz/theory
X-WR-TIMEZONE:America/New_York
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:STANDARD
DTSTART:20221106T020000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20230312T020000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ai1ec-352@www.cs.jhu.edu/~mdinitz/theory
DTSTAMP:20221126T120140Z
CATEGORIES:
CONTACT:
DESCRIPTION:Speaker: Maryam Negahbani\nAffiliation: Dartmouth University\nT
itle: “Revisiting Priority k-Center: Fairness and Outliers\nAbstract:\nClu
stering is a fundamental unsupervised learning and facility location probl
em extensively studied in the literature. I will talk about a clustering p
roblem called “priority k-center” introduced by Plesnik (in Disc. Appl. M
ath. 1987). Given a metric space on n points X\, with distance function d\
, an integer k\, and radius r_v for each point v in X\, the goal is to cho
ose k points S as “centers” to minimize the maximum distance of a point v
to S divided by r_v. For uniform r_v’s this is precisely the “k-center” pr
oblem where the objective is to minimize the maximum distance of any point
to S. In the priority version\, points with smaller r_v are prioritized t
o be closer to S. Recently\, a special case of this problem was studied in
the context of “individually fair clustering” by Jung et al.\, FORC 2020
. This notion of fairness forces S to open a center in every “densely popu
lated area” by setting r_v to be v’s distance to its closest (n/k)-th neig
hbor.\nIn this talk\, I show how to approximate priority k-center with out
liers: When for a given integer z\, you are allowed to throw away z points
as outliers and minimize the objective over the rest of the points. We sh
ow there is 9-approximation\, which is morally a 5\, if you have constant
many types of radii or if your radii are powers of 2. This is via an LP-aw
are reduction to min-cost max-flow and is general enough that could handle
Matroid constraints on facilities (where instead of asking to pick at mos
t k facilities\, you are asked to pick facilities that are independent in
a given matroid). Things become quite interesting for priority knapsack-ce
nter with outliers: where opening each center costs something and you have
a limited budget to spend on your solution S. In this case\, we do not kn
ow how to solve the corresponding flow problem\, so we alter our reduction
to reduce to a simpler problem we do know how to solve taking a hit of +5
in the approximation ratio. There are still many open problems in this wo
rk\, in addition to solving the flow problem in the knapsack case\, the be
st LP integrality gap we know for priority k-center with outliers is 3.
DTSTART;TZID=America/New_York:20210331T120000
DTEND;TZID=America/New_York:20210331T130000
LOCATION:https://wse.zoom.us/j/91450299380
SEQUENCE:0
SUMMARY:[Theory Seminar] Maryam Negahbani
URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-maryam-nega
hbani/
X-COST-TYPE:free
X-ALT-DESC;FMTTYPE=text/html:\\n\\n\\n\\n\\nSpeaker: Mary
am Negahbani

\nAffiliation: Dartmouth University

\nTitle: “Revi
siting Priority k-Center: Fairness and Outliers

\nAbstract:

\nC
lustering is a fundamental unsupervised learning and facility location pro
blem extensively studied in the literature. I will talk about a clustering
problem called “priority k-center” introduced by Plesnik (in Disc. Appl.
Math. 1987). Given a metric space on n points X\, with distance function
d\, an integer k\, and radius r_v for each point v in X\, the goal is to c
hoose k points S as “centers” to minimize the maximum distance of a point
v to S divided by r_v. For uniform r_v’s this is precisely the “k-center”
problem where the objective is to minimize the maximum distance of any poi
nt to S. In the priority version\, points with smaller r_v are prioritized
to be closer to S. Recently\, a special case of this problem was studied
in the context of “individually fair clustering” by Jung et al.\, FORC 20
20. This notion of fairness forces S to open a center in every “densely po
pulated area” by setting r_v to be v’s distance to its closest (n/k)-th ne
ighbor.

\nIn this talk\, I show how to approximate priority k-center
with outliers: When for a given integer z\, you are allowed to throw away
z points as outliers and minimize the objective over the rest of the poin
ts. We show there is 9-approximation\, which is morally a 5\, if you have
constant many types of radii or if your radii are powers of 2. This is via
an LP-aware reduction to min-cost max-flow and is general enough that cou
ld handle Matroid constraints on facilities (where instead of asking to pi
ck at most k facilities\, you are asked to pick facilities that are indepe
ndent in a given matroid). Things become quite interesting for priority kn
apsack-center with outliers: where opening each center costs something and
you have a limited budget to spend on your solution S. In this case\, we
do not know how to solve the corresponding flow problem\, so we alter our
reduction to reduce to a simpler problem we do know how to solve taking a
hit of +5 in the approximation ratio. There are still many open problems i
n this work\, in addition to solving the flow problem in the knapsack case
\, the best LP integrality gap we know for priority k-center with outliers
is 3.

\n
END:VEVENT
END:VCALENDAR