Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems

DOI10.1137/19M126918XOpenAlexW3207977933MaRDI QIDQ5860477FDOQ5860477

Authors: René A. Sitters 

Publication date: 19 November 2021

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

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

Recommendations

• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
• Approximation schemes for minimum latency problems
• Approximation Schemes for Minimum Latency Problems
• The \(k\)-traveling repairmen problem
• The complexity of the travelling repairman problem

zbMATH Keywords

approximation algorithmsinterval orderstotal completion timetraveling repairmanminimum latency tour

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Paths and cycles (05C38) Transportation, logistics and supply chain management (90B06)

Cites Work

• On the approximability of single-machine scheduling with precedence constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• Complexity of Scheduling under Precedence Constraints
• An improved approximation ratio for the minimum latency problem
• The minimum latency problem
• Approximation schemes for minimum latency problems
• A Faster, Better Approximation Algorithm for the Minimum Latency Problem
• The complexity of the travelling repairman problem
• Approximation Schemes for Minimum Latency Problems
• Title not available (Why is that?)
• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
• Heuristics for the traveling repairman problem with profits
• Special cases of traveling salesman and repairman problems with time windows
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Title not available (Why is that?)
• A note on the traveling repairman problem
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Title not available (Why is that?)
• Approximating min sum set cover
• A subset spanner for Planar graphs, with application to subset TSP
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Directed Minimum Latency Problem
• News from the online traveling repairman.
• Title not available (Why is that?)
• On the approximability of average completion time scheduling under precedence constraints.
• A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• Approximation algorithms for minimizing average distortion

Cited In (7)

• Geometric spanning trees minimizing the Wiener index
• Minimizing latency of capacitated \(k\)-tours
• LATIN 2004: Theoretical Informatics
• Polynomial time algorithms for some minimum latency problems
• Approximation Algorithms for Capacitated k-Travelling Repairmen Problems.
• Approximating the \(k\)-traveling repairman problem with repair times
• Geometric spanning trees minimizing the Wiener index

This page was built for publication: Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems

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