Polynomial time algorithms for some minimum latency problems

DOI10.1016/S0020-0190(00)00102-2MaRDI QIDQ294831zbMATH OpenFDO

Authors Bang Ye Wu

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000001022?np=y

zbMATH Keywords

dynamic programmingminimum latency problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Recommendations

• scientific article; zbMATH DE number 2079325
• Approximation Schemes for Minimum Latency Problems
• Approximation schemes for minimum latency problems
• A Faster, Better Approximation Algorithm for the Minimum Latency Problem
• Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
• An improved approximation ratio for the minimum latency problem
• scientific article; zbMATH DE number 871910
• The minimum latency problem
• Algorithms for minimizing maximum lateness with unit length tasks and resource constraints

Cites work

• scientific article; zbMATH DE number 2102754 (Why is no real title available?)
• scientific article; zbMATH DE number 871910 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• Approximation schemes for minimum latency problems
• The complexity of the travelling repairman problem
• The delivery man problem on a tree network
• The minimum latency problem

Cited in

(15)

• scientific article; zbMATH DE number 1003275 (Why is no real title available?)
• Profit-based latency problems on the line
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Exact algorithms for the minimum latency problem
• Two improved formulations for the minimum latency problem
• Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem
• scientific article; zbMATH DE number 2090008 (Why is no real title available?)
• A note on the traveling repairman problem
• Approximation schemes for minimum latency problems
• Minimizing total weighted latency in home healthcare routing and scheduling with patient prioritization
• Hybrid evolutionary search for the traveling repairman problem with profits
• Computing the optimal IO sequences of a protocol in polynomial time
• Approximation algorithms for the a priori traveling repairman
• Weighted online minimum latency problem with edge uncertainty
• Waiting for a Bat to Fly By (in Polynomial Time)

This page was built for publication: Polynomial time algorithms for some minimum latency problems

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