Almost sure asymptotic optimality for online routing and machine scheduling problems

DOI10.1002/net.20309zbMath1211.68517OpenAlexW4233311280MaRDI QIDQ3057128

Patrick Jaillet, Michael R. Wagner

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20309

zbMATH Keywords

machine schedulingonline algorithmsroutingtraveling repairman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items (3)

An approximate dynamic programming approach for <scp>production‐delivery</scp> scheduling under non‐stationary demand ⋮ Continuous approximation formulas for location problems ⋮ Weighted online minimum latency problem with edge uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• News from the online traveling repairman.
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• Approximation Techniques for Average Completion Time Scheduling
• Single Machine Scheduling with Release Dates
• The minimum latency problem
• An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
• Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses
• LP-Based Online Scheduling: From Single to Parallel Machines
• Special cases of traveling salesman and repairman problems with time windows
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Unrelated Machines by Randomized Rounding
• Probabilistic Analysis of Unit-Demand Vehicle Routeing Problems
• An experimental study of online scheduling algorithms
• Computing and Combinatorics
• Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates
• On-line single-server dial-a-ride problems

This page was built for publication: Almost sure asymptotic optimality for online routing and machine scheduling problems