Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines
Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines
复制标题
一类并行同机集成网络设计与调度问题的多项式时间逼近方案
DOI：
10.1007/978-3-031-18530-4_24
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Shioura Akiyoshi
中科院分区：
文献类型：
--
作者：
Saito Yusuke;Shioura Akiyoshi
在集成网络设计与调度问题（INDS-P）中，要求利用并行机对图中的边进行修复，使网络的性能得到一定程度的恢复，目标是最小化完成边修复所需的最大完工时间.本文的主要目的是表明多项式时间近似计划存在的某些类的问题（INDS-P），包括最小生成树，最短路径，最大流与单位容量，最大重量匹配的问题。
In the integrated network design and scheduling problem (INDS-P), 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 paper is to show that polynomial-time approximation schemes exist for some class of the problem (INDS-P), including the problems associated with minimum spanning tree, shortest path, maximum flow with unit capacity, and maximum-weight matching.