講演抄録/キーワード |
講演名 |
2018-12-23 14:35
フローネットワークの辺負荷率平準化問題に対するLPラウンディングを用いた近似アルゴリズムの提案 ○春日 輝・篠宮紀彦(創価大) CAS2018-111 ICD2018-95 CPSY2018-77 エレソ技報アーカイブへのリンク:ICD2018-95 |
抄録 |
(和) |
本稿では,複数のコントローラによって分散管理された情報ネットワークにおける通信リンクの負荷を平準化する手法を提案した.まず,分散管理された情報ネットワークをフローネットワークとしてモデル化し,辺の容量に対する流量(フロー)との比を負荷率として定義し,この負荷率を平準化するフローの経路を求める問題を,Unsplittable flow Edge Load factor Balancing(UELB)問題として定式化した.また,UELB 問題を混合整数計画問題として再定式化し,問題を線形緩和して最適解の下界を求め,LP ラウンディングを用いて問題に対する近似アルゴリズムを設計した. |
(英) |
This paper proposes a method for leveling traffic load of communication links in a distributed management network with multiple controllers. Our study has modeled the distributed management network as a flow network and defined the ratio of flow to capacity in an edge as a load-factor. On that network, an unsplittable-flow edge-load-factor balancing (UELB) problem has been formulated for finding the flow and the corresponding path leveling the load-factor. This paper reformulates the UELB problem as a mixed integer programming problem, while a lower bound of the optimal solution is given by a linear programming relaxation and an approximation algorithm for the problem is designed with using LP rounding. |
キーワード |
(和) |
分散管理ネットワーク / ネットワークフロー問題 / 負荷平準化 / LP ラウンディング / / / / |
(英) |
distributed management network / network flow problem / load balancing / LP rounding / / / / |
文献情報 |
信学技報, vol. 118, no. 373, CAS2018-111, pp. 131-135, 2018年12月. |
資料番号 |
CAS2018-111 |
発行日 |
2018-12-14 (CAS, ICD, CPSY) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2018-111 ICD2018-95 CPSY2018-77 エレソ技報アーカイブへのリンク:ICD2018-95 |
研究会情報 |
研究会 |
ICD CPSY CAS |
開催期間 |
2018-12-21 - 2018-12-23 |
開催地(和) |
ホテルアトールエメラルド宮古島 |
開催地(英) |
|
テーマ(和) |
学生・若手研究会 |
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
CAS |
会議コード |
2018-12-ICD-CPSY-CAS |
本文の言語 |
日本語 |
タイトル(和) |
フローネットワークの辺負荷率平準化問題に対するLPラウンディングを用いた近似アルゴリズムの提案 |
サブタイトル(和) |
|
タイトル(英) |
An approximation algorithm with LP rounding for an unsplittable flow edge load factor balancing problem in a flow network |
サブタイトル(英) |
|
キーワード(1)(和/英) |
分散管理ネットワーク / distributed management network |
キーワード(2)(和/英) |
ネットワークフロー問題 / network flow problem |
キーワード(3)(和/英) |
負荷平準化 / load balancing |
キーワード(4)(和/英) |
LP ラウンディング / LP rounding |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
春日 輝 / Hikaru Kasuga / カスガ ヒカル |
第1著者 所属(和/英) |
創価大学 (略称: 創価大)
Soka University (略称: Soka Univ.) |
第2著者 氏名(和/英/ヨミ) |
篠宮 紀彦 / Norihiko Shinomiya / シノミヤ ノリヒコ |
第2著者 所属(和/英) |
創価大学 (略称: 創価大)
Soka University (略称: Soka Univ.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2018-12-23 14:35:00 |
発表時間 |
20分 |
申込先研究会 |
CAS |
資料番号 |
CAS2018-111, ICD2018-95, CPSY2018-77 |
巻番号(vol) |
vol.118 |
号番号(no) |
no.373(CAS), no.374(ICD), no.375(CPSY) |
ページ範囲 |
pp.131-135 |
ページ数 |
5 |
発行日 |
2018-12-14 (CAS, ICD, CPSY) |