The Directed Minimum Latency Problem

DOI10.1007/978-3-540-85363-3_16zbMath1159.68674OpenAlexW1492330513MaRDI QIDQ3541796

R. Ravi, Viswanath Nagarajan

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

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

Related Items (9)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ An Improved Integrality Gap for Asymmetric TSP Paths ⋮ 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 ⋮ Minimising average passenger waiting time in personal rapid transit systems ⋮ The asymmetric traveling salesman path LP has constant integrality ratio ⋮ Unnamed Item ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems

Cites Work

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

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