The minimum latency problem

DOI10.1145/195058.195125zbMath1345.90073arXivmath/9409223OpenAlexW1966793805MaRDI QIDQ2817608

Prabhakar Raghavan, Madhu Sudan, Don Coppersmith, Bill Pulleyblank, Prasad Chalasani, Avrim L. Blum

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (69)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ Exact algorithms for the minimum latency problem ⋮ Polynomial time algorithms for some minimum latency problems ⋮ Some notes on bounded starwidth graphs ⋮ Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ Maintenance scheduling of geographically distributed assets with prognostics information ⋮ A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones ⋮ Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem ⋮ Heuristics for the traveling repairman problem with profits ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ Counting and optimising maximum phylogenetic diversity sets ⋮ Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems ⋮ On the existence of schedules that are near-optimal for both makespan and total weighted completion time ⋮ The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ Approximation algorithms for the a priori traveling repairman ⋮ A POPMUSIC approach for the multi-depot cumulative capacitated vehicle routing problem ⋮ A sub-modular receding horizon solution for mobile multi-agent persistent monitoring ⋮ The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach ⋮ A simple and effective metaheuristic for the minimum latency problem ⋮ Search and delivery man problems: when are depth-first paths optimal? ⋮ The multi-vehicle cumulative covering tour problem ⋮ A performance study on multi improvement neighborhood search strategy ⋮ Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem ⋮ Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining ⋮ Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications ⋮ An iterated local search algorithm for latency vehicle routing problems with multiple depots ⋮ News from the online traveling repairman. ⋮ A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ The delivery man problem with time windows ⋮ From theory to practice: maximizing revenues for on-line dial-a-ride ⋮ Adaptive Submodular Ranking and Routing ⋮ Routing vehicles to minimize fuel consumption ⋮ The Directed Minimum Latency Problem ⋮ Hybrid evolutionary search for the traveling repairman problem with profits ⋮ Approximating the \(k\)-traveling repairman problem with repair times ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ Profit-based latency problems on the line ⋮ The expanding search ratio of a graph ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ A truck and drones model for last-mile delivery: a mathematical model and heuristic approach ⋮ Hybrid optimization methods for time-dependent sequencing problems ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ Query strategies for priced information ⋮ Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem ⋮ An effective memetic algorithm for the cumulative capacitated vehicle routing problem ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ An adaptive large neighborhood search approach for multiple traveling repairman problem with profits ⋮ The Chinese deliveryman problem ⋮ Almost sure asymptotic optimality for online routing and machine scheduling problems ⋮ Probabilistic Analysis of Unit-Demand Vehicle Routeing Problems ⋮ The A priori traveling repairman problem ⋮ Minimizing latency of capacitated \(k\)-tours ⋮ On-line single-server dial-a-ride problems ⋮ On combining machine learning with decision making ⋮ A hybrid reactive GRASP heuristic for the risk-averse \(k\)-traveling repairman problem with profits ⋮ A new formulation for the traveling deliveryman problem ⋮ A metaheuristic for the delivery man problem with time windows ⋮ The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices ⋮ Finding the maximum multi improvement on neighborhood exploration ⋮ An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem ⋮ An improved approximation ratio for the minimum latency problem ⋮ The multi-depot \(k\)-traveling repairman problem ⋮ A constant-factor approximation algorithm for the \(k\)-MST problem ⋮ A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Solving the traveling delivery person problem with limited computational time ⋮ General bounds for incremental maximization ⋮ A heuristic for cumulative vehicle routing using column generation

This page was built for publication: The minimum latency problem