A Faster, Better Approximation Algorithm for the Minimum Latency Problem

DOI10.1137/07068151XzbMath1181.68326OpenAlexW2009279347MaRDI QIDQ3532573

Aaron Archer, David P. Williamson, Asaf Levin

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

Lagrangian relaxationapproximation algorithmminimum latency problemtraveling repairmanprize-collecting Steiner tree

Mathematics Subject Classification ID

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

Related Items (13)

The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach ⋮ A 16-competitive algorithm for hierarchical median problem ⋮ Approximation algorithm for minimizing total latency in machine scheduling with deliveries ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ An effective memetic algorithm for the cumulative capacitated vehicle routing problem ⋮ Minimizing latency of capacitated \(k\)-tours ⋮ On combining machine learning with decision making ⋮ An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Solving the traveling delivery person problem with limited computational time

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