1 citations · 2 across the 5 of their papers we have counts for
12 papers · 1 filter
Approximating Traveling Salesman Problems Using a Bridge Lemma
Martin Böhm, Zachary Friggstad, Tobias Mömke +1
We give improved approximations for two metric Traveling Salesman Problem (TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a subset of nodes $o_1, \ldots, o_…
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka +6
We consider the well-studied Robust -Clustering problem, which generalizes the classic -Median, -Means, and -Center problems. Given a constant , the input…
Parameterized Approximation Schemes for Clustering with General Norm Objectives
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka +6
This paper considers the well-studied algorithmic regime of designing a -approximation algorithm for a -clustering problem that runs in time (sometimes ca…
Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
Parinya Chalermsook, Matthias Kaul, Matthias Mnich +3
The fundamental sparsest cut problem takes as input a graph together with the edge costs and demands, and seeks a cut that minimizes the ratio between the costs and demands acr…
On Minimum Generalized Manhattan Connections
Antonios Antoniadis, Margarita Capretto, Parinya Chalermsook +5
We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points in the plane, together with a subset of pairs of points in (wh…
PTAS for Steiner Tree on Map Graphs
Jarosław Byrka, Mateusz Lewandowski, Syed Mohammad Meesum +2
We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map grap…