Approximation Schemes for Minimum Latency Problems

DOI10.1137/S0097539701399654MaRDI QIDQ4429687zbMATH OpenOpenAlexFDO

Authors George Karakostas, Sanjeev Arora

Publication date 28 September 2003

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

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

zbMATH Keywords

approximation algorithmsminimum latency tourquasi-polynomial approximation schemesrandomized search ratiosearch ratiotraveling repairmanvehicle routing

Mathematics Subject Classification ID

Paths and cycles (05C38) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Recommendations

• Approximation schemes for minimum latency problems
• scientific article; zbMATH DE number 871910
• LATIN 2004: Theoretical Informatics
• The minimum latency problem
• The \(k\)-traveling repairmen problem

Cited in

(31)

• An improved approximation ratio for the minimum latency problem
• The expanding search ratio of a graph
• 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
• The Chinese deliveryman problem
• A constant-factor approximation for directed latency in quasi-polynomial time
• Search and delivery man problems: when are depth-first paths optimal?
• Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints
• Approximation algorithms for the traveling repairman and speeding deliveryman problems
• Approximation algorithms for the a priori traveling repairman
• Approximation schemes for minimum latency problems
• Polynomial time algorithms for some minimum latency problems
• Approximation algorithms for multi-robot patrol-scheduling with min-max latency
• Minimization of the total completion time for asynchronous transmission in a packet data-transmission system
• Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows
• Approximation algorithms for min-max path cover problems with service handling time
• scientific article; zbMATH DE number 2079396 (Why is no real title available?)
• scientific article; zbMATH DE number 1507215 (Why is no real title available?)
• scientific article; zbMATH DE number 871910 (Why is no real title available?)
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• The \(k\)-traveling repairmen problem
• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
• scientific article; zbMATH DE number 6297719 (Why is no real title available?)
• Algorithms – ESA 2005
• Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
• Minimizing maximum lateness under linear deterioration
• Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
• Traveling repairperson, unrelated machines, and other stories about average completion times
• Minimizing latency of capacitated \(k\)-tours
• On the minimum delay problem
• Exact algorithms for the minimum latency problem

This page was built for publication: Approximation Schemes for Minimum Latency Problems

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