# Generalized Metric Repair on Graphs

Rishi SonthaliaUniversity of Michigan

WHERE:

3901 Beyster BuildingMap

WHEN:

September 20, 2019 @ 10:00 am - 11:00 am

Add to Google Calendar

Add to Google Calendar

SHARE:

Many modern data analysis algorithms either assume or are considerably more efficient if the distances between the data points satisfy a metric. These algorithms include metric learning, clustering, and dimension reduction. As real data sets are noisy, distances often fail to satisfy a metric. For this reason, Gilbert and Jain and Fan et al. introduced the closely related sparse metric repair and metric violation distance problems. The goal of these problems is to repair as few distances as possible to ensure they satisfy a metric. Three variants were considered, one admitting a polynomial time algorithm. The other variants were shown to be APX-hard, and an

In this talk, I will generalize these problems to no longer consider all distances between the data points. That is, we consider a weighted graph

__O(OPT^1/3)____-approximation was given, where____OPT____is the optimal solution size.__In this talk, I will generalize these problems to no longer consider all distances between the data points. That is, we consider a weighted graph

__G____with corrupted weights____w____, and our goal is to find the smallest number of weight modifications so that the resulting weighted graph distances satisfy a metric. I will demonstrate the inherent combinatorial structure of the problem, and present a few theorems about the hardness of the problem. I will also show that for any fixed constant____ς____, for the large class of____ς____-chordal graphs, the problems are fixed parameter tractable. Time permitting, I will then discuss a variant of this problem where we are not given the graph $G$, but learn its structure as well.__