Linear programming-based approximation algorithms for multi-vehicle minimum latency problems: extended abstract

We consider various multi-vehicle versions of the minimum latency problem. There is a fleet of k vehicles located at one or more depot nodes, and we seek a collection of routes for these vehicles that visit all nodes so as to minimize the total latency incurred, which is the sum of the client waiting times. We obtain an 8.497-approximation for the version where vehicles may be located at multiple depots and a 7.183-approximation for the version where all vehicles are located at the same depot, both of which are the first improvements on this problem in a decade. Perhaps more significantly, our algorithms exploit various LP relaxations for minimum-latency problems. We show how to effectively leverage two classes of LPs---configuration LPs and bidirected LP relaxations---that are often believed to be quite powerful but have only sporadically been effectively leveraged for network-design and vehicle-routing problems. This gives the first concrete evidence of the effectiveness of LP relaxations for this class of problems.The 8.497-approximation the multiple-depot version is obtained by rounding a near-optimal solution to an underlying configuration LP for the problem. The 7.183-approximation can be obtained both via rounding a bidirected LP for the single-depot problem or via more combinatorial means. The latter approach uses a bidirected LP to obtain the following key result that is of independent interest: for any k, we can efficiently compute a rooted tree that is at least as good, with respect to the prize-collecting objective (i.e., edge cost + number of uncovered nodes) as the best collection of k rooted paths. This substantially generalizes a result of Chaudhuri et al. [11] for k = 1, yet our proof is significantly simpler. Our algorithms are versatile and extend easily to handle various extensions involving: (i) weighted sum of latencies, (ii) constraints specifying which depots may serve which nodes, (iii) node service times.Finally, we propose a configuration LP that sheds further light on the power of LP relaxations for minimum-latency problems. We prove that the integrality gap of this LP is at most 3.592, even for the multi-depot problem, both via an efficient rounding procedure, and by showing that it is at least as powerful as a stroll-based lower bound that is oft-used for minimum-latency problems; the latter result implies an integrality gap of at most 3.03 when k = 1. Although, we do not know how to solve this LP in general, it can be solved (near-optimally) when k = 1, and this yields an LP-relative 3.592-approximation for the single-vehicle problem, matching (essentially) the current-best approximation ratio for this problem.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.