BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.18.4.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261201T163000
DTEND;TZID=Asia/Seoul:20261201T173000
DTSTAMP:20261109T145436Z
CREATED:20261106T160706Z
LAST-MODIFIED:20261109T145436Z
UID:13963-1796142600-1796146200@dimag.ibs.re.kr
SUMMARY:Saeed Odak\, Approximation Schemes for Hyperbolic TSP and Steiner Tree
DESCRIPTION:We give an approximation scheme for the TSP in $d$-dimensional hyperbolic space that has nearly optimal dependence on $\varepsilon$ under SH. For any fixed dimension $d\geq 2$ and for any $\varepsilon>0$ our randomized algorithm gives a $(1+\varepsilon)$-approximation in time $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$. We also provide an algorithm for the hyperbolic Steiner tree problem with the same running time. \n\n\n\nOur algorithm is an Arora-style dynamic program based on a randomly shifted hierarchical decomposition. However\, we introduce a new hierarchical decomposition called the hybrid hyperbolic quadtree to achieve the desired large-scale structure\, which deviates significantly from the recently proposed hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen (JoCG’25). Moreover\, we have a new non-uniform portal placement\, and our structure theorem employs a new weighted crossing analysis. We believe that these techniques could form the basis for further developments in geometric optimization in curved spaces. \n\n\n\nThis is a joint work with Sándor Kisfaludi-Bak\, Satyam Singh\, and Geert van Wordragen.
URL:https://dimag.ibs.re.kr/event/2026-12-01/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR