An improved approximation ratio for the minimum latency problem

DOI10.1007/BF01585867zbMATH Open0920.90138MaRDI QIDQ1290636FDOQ1290636

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)

Recommendations

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

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)

Cites Work

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

Cited In (43)

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

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)