BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230110T120000Z
UID:98b6c0e58b126c3134a5ca105b7ac1b7-388
DTSTAMP:19700101T120011Z
DESCRIPTION:Hardness of Approximating Discrete Steiner Tree in L_p metrics
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/388/hardness-of-approximating-discrete-steiner-tree-in-l_p-metrics/
SUMMARY: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	https://karthikcs.org/

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


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


Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul
DTSTART:20230110T120000Z
END:VEVENT
END:VCALENDAR