Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines

• Item type: SIG Technical Reports(1)
• 公開日: 2022-05-12
• タイトル: Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines
• タイトル / 言語: en
• タイトル: Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Industrial Engineering and Economics, Tokyo Institute of Technology
• 著者所属: Department of Industrial Engineering and Economics, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Industrial Engineering and Economics, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Industrial Engineering and Economics, Tokyo Institute of Technology
• 著者名: Yusuke, Saito; Akiyoshi, Shioura
• 著者名(英): Yusuke, Saito; Akiyoshi, Shioura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-188, 号 9, p. 1-6, 発行日 2022-05-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会