Showing cs.CGShow all
2 papers · 1 filter
cs.CG2026
Online Algorithms for Geometric Independent Set
Minati De, Satyam Singh
In the classical online model, the maximum independent set problem admits an lower bound on the competitive ratio even for interval graphs, motivating the study of the probl…
cs.CG2026
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh +1
We give an approximation scheme for the TSP in -dimensional hyperbolic space that has optimal dependence on under Gap-ETH. For any fixed dimension and fo…