Seminars

View all Seminars  |  Download ICal for this event

Hardness of Approximating Discrete Steiner Tree in L_p metrics

Series: Bangalore Theory Seminars

Speaker: Karthik C. S. Rutgers University

Date/Time: Jan 10 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
In the Discrete Steiner Tree problem (DST), we are given as input two sets of points in a metric space, called terminals and facilities respectively, and the goal is to find the minimum-cost tree connecting the terminals, by possibly introducing new points (called Steiner points) from the set of facilities, as nodes in the solution. It was known that DST is APX hard in the L_1 metric by Trevisan (SICOMP 00) and in the Graph metric (and consequently, L_infinity metric ) by Chlebík and Chlebíková (TCS 08). It was open to rule out PTAS for DST in every other popular metric.

In this talk, I will sketch the proof of APX hardness of DST in every Lp metric (in particular the Euclidean metric), edit metric, and Ulam metric.

The talk is based on joint work with Henry Fleischmann and Surya Teja Gavva.


Speaker Website Link

Microsoft teams link:

Link


Acknowledging the support from the Kirani family for generously supporting the seminar series.


Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul