An improved approximation ratio for the minimum latency problem

DOI10.1007/BF01585867MaRDI QIDQ1290636zbMATH OpenFDO

Authors 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

approximation algorithmstraveling salesman problemapproximation 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)

Recommendations

• scientific article; zbMATH DE number 871910
• The minimum latency problem
• scientific article; zbMATH DE number 6297719
• Approximation Schemes for Minimum Latency Problems

Cites work

• scientific article; zbMATH DE number 1256763 (Why is no real title available?)
• scientific article; zbMATH DE number 1263203 (Why is no real title available?)
• scientific article; zbMATH DE number 1263205 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A note on the prize collecting traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Heuristic analysis, linear programming and branch and bound
• P-Complete Approximation Problems
• Searching in the plane
• Special cases of traveling salesman and repairman problems with time windows
• Survivable networks, linear programming relaxations and the parsimonious property
• The Delivery Man Problem and Cumulative Matroids
• The complexity of the travelling repairman problem
• The delivery man problem on a tree network
• The minimum latency problem

Cited in

(42)

• Search and delivery man problems: when are depth-first paths optimal?
• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• A water-filling primal-dual algorithm for approximating nonlinear covering problems
• Minimizing latency in post-disaster road clearance operations
• Incremental medians via online bidding
• A new formulation for the traveling deliveryman problem
• scientific article; zbMATH DE number 2079325 (Why is no real title available?)
• General bounds for incremental maximization
• Approximation algorithm for minimizing total latency in machine scheduling with deliveries
• An improved online algorithm for the traveling repairperson problem on a line
• Exact algorithms for the minimum latency problem
• A simple and effective metaheuristic for the minimum latency problem
• A branch-and-price algorithm for the minimum latency problem
• The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach
• A truck and drones model for last-mile delivery: a mathematical model and heuristic approach
• A Faster, Better Approximation Algorithm for the Minimum Latency Problem
• Incremental facility location problem and its competitive algorithms
• The delivery man problem with time windows
• Approximation schemes for minimum latency problems
• The minimum latency problem
• scientific article; zbMATH DE number 1688368 (Why is no real title available?)
• The A priori traveling repairman problem
• An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
• Minimizing latency of capacitated \(k\)-tours
• Discounted reward TSP
• Improved bounds for randomized preemptive online matching
• Minimizing customers' waiting time in a vehicle routing problem with unit demands
• The expanding search ratio of a graph
• On combining machine learning with decision making
• Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
• Heuristics for the traveling repairman problem with profits
• Routing multiple work teams to minimize latency in post-disaster road network restoration
• On the power of lookahead in on-line server routing problems
• Hybrid evolutionary search for the traveling repairman problem with profits
• scientific article; zbMATH DE number 2086925 (Why is no real title available?)
• Polynomial time algorithms for some minimum latency problems
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• scientific article; zbMATH DE number 6297719 (Why is no real title available?)
• Solving the traveling repairman problem with profits: a novel variable neighborhood search approach
• The Directed Minimum Latency Problem
• Approximation algorithms for the a priori traveling repairman
• Routing under uncertainty: the \textit{a priori} traveling repairman problem

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

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