28 citations · 62 across the 18 of their papers we have counts for
28 papers
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_…
Independent set in -Claw-Free Graphs: Conditional -boundedness and the Power of LP/SDP Relaxations
Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi +1
This paper studies -claw-free graphs, exploring the connection between an extremal combinatorics question and the power of a convex program in approximating the maximum-weight i…
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…
Coloring Mixed and Directional Interval Graphs
Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter +3
A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph is a function that assigns to each vertex in…
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…