Almost sure asymptotic optimality for online routing and machine scheduling problems
From MaRDI portal
Publication:3057128
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
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