An improved approximation ratio for the minimum latency problem

DOI10.1007/BF01585867zbMath0920.90138MaRDI QIDQ1290636

Michel X. Goemans, Jon M. Kleinberg

Publication date: 15 September 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

traveling salesman problemapproximation algorithmsapproximation ratiominimum latency problemtraveling repairman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (33)

Exact algorithms for the minimum latency problem ⋮ Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ Heuristics for the traveling repairman problem with profits ⋮ An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs ⋮ Approximation algorithms for the a priori traveling repairman ⋮ Incremental facility location problem and its competitive algorithms ⋮ The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach ⋮ A simple and effective metaheuristic for the minimum latency problem ⋮ Routing multiple work teams to minimize latency in post-disaster road network restoration ⋮ Search and delivery man problems: when are depth-first paths optimal? ⋮ The delivery man problem with time windows ⋮ Improved bounds for randomized preemptive online matching ⋮ Discounted reward TSP ⋮ Approximation algorithm for minimizing total latency in machine scheduling with deliveries ⋮ The Directed Minimum Latency Problem ⋮ Hybrid evolutionary search for the traveling repairman problem with profits ⋮ Minimizing latency in post-disaster road clearance operations ⋮ The expanding search ratio of a graph ⋮ Minimizing customers' waiting time in a vehicle routing problem with unit demands ⋮ A truck and drones model for last-mile delivery: a mathematical model and heuristic approach ⋮ On the power of lookahead in on-line server routing problems ⋮ Solving the traveling repairman problem with profits: a novel variable neighborhood search approach ⋮ Incremental medians via online bidding ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ The A priori traveling repairman problem ⋮ Minimizing latency of capacitated \(k\)-tours ⋮ On combining machine learning with decision making ⋮ A new formulation for the traveling deliveryman problem ⋮ An Improved Online Algorithm for the Traveling Repairperson Problem on a Line ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ General bounds for incremental maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• Survivable networks, linear programming relaxations and the parsimonious property
• Searching in the plane
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• The delivery man problem on a tree network
• The minimum latency problem
• The complexity of the travelling repairman problem
• Heuristic analysis, linear programming and branch and bound
• Special cases of traveling salesman and repairman problems with time windows
• P-Complete Approximation Problems
• The Delivery Man Problem and Cumulative Matroids
• A General Approximation Technique for Constrained Forest Problems

This page was built for publication: An improved approximation ratio for the minimum latency problem