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

DOI10.1137/1.9781611973730.35MaRDI QIDQ5362984zbMATH OpenOpenAlexFDO

Authors Ian Post, Chaitanya Swamy

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.4573

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Linear programming (90C05) Integer programming (90C10)

Abstract: We consider various {em 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---{em configuration LPs} and {em 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. 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.

Recommendations

• scientific article; zbMATH DE number 6297719
• Minimizing latency of capacitated \(k\)-tours
• A Faster, Better Approximation Algorithm for the Minimum Latency Problem

Cited in

(9)

• Linear time approximation schemes for vehicle scheduling problems
• A constant-factor approximation for directed latency in quasi-polynomial time
• Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
• A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
• Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs
• A better-than-1.6-approximation for prize-collecting TSP
• Constant-factor approximation to deadline TSP and related problems in (almost) quasi-polytime
• Minimizing latency of capacitated \(k\)-tours
• Approximating prize-collecting variants of tsp

This page was built for publication: Linear programming-based approximation algorithms for multi-vehicle minimum latency problems (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5362984)