The Directed Minimum Latency Problem

DOI10.1007/978-3-540-85363-3_16MaRDI QIDQ3541796zbMATH OpenOpenAlexFDO

Authors Viswanath Nagarajan, R. Ravi

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85363-3_16

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A constant-factor approximation for directed latency in quasi-polynomial time
• Asymmetric traveling salesman path and directed latency problems
• Asymmetric traveling salesman path and directed latency problems
• The minimum latency problem
• scientific article; zbMATH DE number 871910

Cites work

• An improved approximation ratio for the minimum latency problem
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• scientific article; zbMATH DE number 5899262 (Why is no real title available?)
• scientific article; zbMATH DE number 5764858 (Why is no real title available?)
• scientific article; zbMATH DE number 4103110 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• Makespan Minimization in No-Wait Flow Shops: A Polynomial Time Approximation Scheme
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• P-Complete Approximation Problems
• Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems
• Solution of the Flowshop-Scheduling Problem with No Intermediate Queues
• Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
• The complexity of the travelling repairman problem
• The delivery man problem on a tree network
• The minimum latency problem
• Traveling salesman path problems

Cited in

(13)

• A simple and effective metaheuristic for the minimum latency problem
• A constant-factor approximation for directed latency in quasi-polynomial time
• An adaptive large neighborhood search approach for multiple traveling repairman problem with profits
• Charlemagne's Challenge: The Periodic Latency Problem
• scientific article; zbMATH DE number 6347354 (Why is no real title available?)
• scientific article; zbMATH DE number 2090008 (Why is no real title available?)
• Asymmetric traveling salesman path and directed latency problems
• Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
• A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
• Minimising average passenger waiting time in personal rapid transit systems
• Constant-factor approximation to deadline TSP and related problems in (almost) quasi-polytime
• On the minimum delay problem
• The minimum backlog problem

This page was built for publication: The Directed Minimum Latency Problem

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