12 citations · 15 across the 9 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.DS2009
Asymmetric Traveling Salesman Path and Directed Latency Problems
Zachary Friggstad, Mohammad R. Salavatipour, Zoya Svitkina
We study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric and two specified node…
cs.CG2009★ 12 cited
A Weakly-Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
Imran A. Pirwani, Mohammad R. Salavatipour
We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NP-hard and various constant factor ap…