On the maximum quadratic assignment problem
Viswanath Nagarajan, Maxim Sviridenko
SODA 2009
We study the distance constrained vehicle routing problem (DVRP) (Laporte et al., Networks 14 (1984), 47-61, Li et al., Oper Res 40 (1992), 790-799): given a set of vertices in a metric space, a specified depot, and a distance bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D. This problem is NP-complete, even when the underlying metric is induced by a weighted star. Our main result is a 2-approximation algorithm for DVRP on tree metrics; we also show that no approximation factor better than 1.5 is possible unless P = NP. For the problem on general metrics, we present a (O(log 1/ε),1 + ε) -bicriteria approximation algorithm: i.e., for any ε > 0, it obtains a solution violating the length bound by a 1 + ε factor while using at most O(log 1/ε) times the optimal number of vehicles. © 2011 Wiley Periodicals, Inc.
Viswanath Nagarajan, Maxim Sviridenko
SODA 2009
Nikhil Bansal, Rohit Khandekar, et al.
STOC 2008
Viswanath Nagarajan, R. Ravi, et al.
Operations Research Letters
Viswanath Nagarajan, R. Ravi
Algorithmica (New York)