NOTE ON POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR INTEGRATED NETWORK DESIGN AND SCHEDULING PROBLEMS
Open Access
- 31 October 2024
- journal article
- Published by The Operations Research Society of Japan in Journal of the Operations Research Society of Japan
- Vol. 67 (4) , 111-125
Abstract
In the integrated network design and scheduling (INDS) problem, we are asked to repair edges in a graph by using parallel machines so that the performance of the network is recovered by a certain level, and the objective is to minimize the makespan required to finish repairing edges. The main aim of this note is to show that polynomial-time approximation schemes exist for various families of the INDS problems with a constant number of parallel machines, including the problems associated with minimum spanning tree, shortest path, maximum edge-disjoint paths, and maximum-weight matching.Keywords
This publication has 21 references indexed in Scilit:
- Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines2022
- Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penaltiesJournal of Combinatorial Optimization, 2022
- Network construction/restoration problems: cycles and complexityJournal of Combinatorial Optimization, 2021
- Approximation algorithms for the multiprocessor scheduling with submodular penaltiesOptimization Letters, 2021
- Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rulesNetworks, 2014
- A survey on offline scheduling with rejectionJournal of Scheduling, 2012
- Budgeted matching and budgeted matroid intersection via the gasoline puzzleMathematical Programming, 2009
- Approximation Algorithms2003
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem1999
- The constrained minimum spanning tree problem1996