Scheduling on a graph with release times
From MaRDI portal
Publication:6204662
DOI10.1007/s10951-021-00680-zOpenAlexW3137217105MaRDI QIDQ6204662
Guo-Chuan Zhang, Wei Yu, Mordecai J. Golin
Publication date: 2 April 2024
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-021-00680-z
Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Improved approximation algorithms for some min-max and minimum cycle cover problems
- Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle
- New inapproximability bounds for TSP
- Approximation results for a min-max location-routing problem
- A \(\frac{5}{3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
- An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
- Linear time approximation schemes for vehicle scheduling problems
- Improved algorithms for single vehicle scheduling on tree/cycle networks
- Better approximability results for min-max tree/cycle/path cover problems
- TSP with bounded metrics
- Approximation Algorithms for Min-Max Cycle Cover Problems
- Approximation results for min-max path cover problems in vehicle routing
- Single-vehicle scheduling problems with release and service times on a line
- Improving Christofides' Algorithm for the s-t Path TSP
- Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times
- Special cases of traveling salesman and repairman problems with time windows
- P-Complete Approximation Problems
- Complexity Of The Single Vehicle Scheduling Problem On Graphs
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
- Vehicle Scheduling on a Graph Revisited
- A 1.5-Approximation for Path TSP
This page was built for publication: Scheduling on a graph with release times
