activity
20002026
most citedApproximation algorithms for TSP with neighborhoods in the plane

193 citations · 363 across the 59 of their papers we have counts for

collaborators
Showing 2015Show all

3 papers · 1 filter

cs.CG2015

Lower bounds on the dilation of plane spanners

Adrian Dumitrescu, Anirban Ghosh

(I) We exhibit a set of 23 points in the plane that has dilation at least , improving the previously best lower bound of for the worst-case dilation of plane spann…

math.CO2015

Problems on Track Runners

Adrian Dumitrescu, Csaba D. Tóth

Consider the circle of length 1 and a circular arc of length . It is shown that there exists , and a schedule for runners along…

cs.CG2015

Constant-Factor Approximation for TSP with Disks

Adrian Dumitrescu, Csaba D. Tóth

We revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constant-ratio approximation for disks in the plane: Given a set of disks in the plane…