Approximation algorithms for the a priori traveling repairman

DOI10.1016/j.orl.2020.07.009zbMath1479.90179arXiv1901.06581OpenAlexW3045467045MaRDI QIDQ2661528

Inge Li Gørtz, Viswanath Nagarajan, Fatemeh Navidi

Publication date: 7 April 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.06581

zbMATH Keywords

approximation algorithmsa priori optimizationtraveling repairman problem

Mathematics Subject Classification ID

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

Related Items

A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones, Stochastic hub location problems with Bernoulli demands

Cites Work

• Unnamed Item
• Polynomial time algorithms for some minimum latency problems
• Deterministic sampling algorithms for network design
• The A priori traveling repairman problem
• Algorithms for the universal and a priori TSP
• An improved approximation ratio for the minimum latency problem
• The minimum latency problem
• Technical Note—Approximation Algorithms for VRP with Stochastic Demands
• Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• Improved Lower Bounds for the Universal and a priori TSP
• The complexity of the travelling repairman problem
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• The Delivery Man Problem and Cumulative Matroids
• Approximation Schemes for Minimum Latency Problems
• A Priori Optimization
• A Vehicle Routing Problem with Stochastic Demand