A Faster, Better Approximation Algorithm for the Minimum Latency Problem

DOI10.1137/07068151XMaRDI QIDQ3532573zbMATH OpenOpenAlexFDO

Authors Aaron Archer, Asaf Levin, David P. Williamson

Publication date 28 October 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/07068151x

zbMATH Keywords

approximation algorithmLagrangian relaxationminimum latency problemprize-collecting Steiner treetraveling repairman

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 2079325
• scientific article; zbMATH DE number 871910
• The \(k\)-traveling repairmen problem
• An improved approximation ratio for the minimum latency problem
• scientific article; zbMATH DE number 2079396

Cited in

(22)

• 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
• Solving the traveling delivery person problem with limited computational time
• Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
• The arc-item-load and related formulations for the cumulative vehicle routing problem
• Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints
• On combining machine learning with decision making
• The minimum latency problem
• Approximation schemes for minimum latency problems
• Polynomial time algorithms for some minimum latency problems
• scientific article; zbMATH DE number 2089222 (Why is no real title available?)
• scientific article; zbMATH DE number 2079325 (Why is no real title available?)
• Exact and Approximation Algorithms for the Expanding Search Problem
• An efficient two-phase metaheuristic algorithm for the time dependent traveling salesman problem
• Linear programming-based approximation algorithms for multi-vehicle minimum latency problems (extended abstract)
• scientific article; zbMATH DE number 6297719 (Why is no real title available?)
• Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
• A guided quantum particle swarm optimization approach for the traveling repairman problem
• Minimizing latency of capacitated \(k\)-tours
• A 16-competitive algorithm for hierarchical median problem
• Approximation algorithm for minimizing total latency in machine scheduling with deliveries
• An effective memetic algorithm for the cumulative capacitated vehicle routing problem

This page was built for publication: A Faster, Better Approximation Algorithm for the Minimum Latency Problem

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