| 講演名 | 2018-12-23 フローネットワークの辺負荷率平準化問題に対するLPラウンディングを用いた近似アルゴリズムの提案 春日 輝(創価大), 篠宮 紀彦(創価大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では，複数のコントローラによって分散管理された情報ネットワークにおける通信リンクの負荷を平準化する手法を提案した．まず，分散管理された情報ネットワークをフローネットワークとしてモデル化し，辺の容量に対する流量（フロー）との比を負荷率として定義し，この負荷率を平準化するフローの経路を求める問題を，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 |
| 資料番号 | CAS2018-111,ICD2018-95,CPSY2018-77 |
| 発行日 | 2018-12-14 (CAS, ICD, CPSY) |
| 研究会情報 | |
| 研究会 | ICD / CPSY / CAS |
|---|---|
| 開催期間 | 2018/12/21(から3日開催) |
| 開催地（和） | ホテルアトールエメラルド宮古島 |
| 開催地（英） | |
| テーマ（和） | 学生・若手研究会 |
| テーマ（英） | |
| 委員長氏名（和） | 日高 秀人(ルネサス エレクトロニクス) / 中野 浩嗣(広島大) / 岡崎 秀晃(湘南工科大) |
| 委員長氏名（英） | Hideto Hidaka(Renesas) / Koji Nakano(Hiroshima Univ.) / Hideaki Okazaki(Shonan Inst. of Tech.) |
| 副委員長氏名（和） | 永田 真(神戸大) / 入江 英嗣(東大) / 三吉 貴史(富士通研) / 山脇 大造(日立) |
| 副委員長氏名（英） | Makoto Nagata(Kobe Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) / Taizo Yamawaki(Hitachi) |
| 幹事氏名（和） | 橋本 隆(パナソニック) / 夏井 雅典(東北大) / 大川 猛(宇都宮大) / 高前田 伸也(北大) / 橘 俊宏(湘南工科大) / 中村 洋平(日立) |
| 幹事氏名（英） | Takashi Hashimoto(Panasonic) / Masanori Natsui(Tohoku Univ.) / Takeshi Ohkawa(Utsunomiya Univ.) / Shinya Takameda(Hokkaido Univ.) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) |
| 幹事補佐氏名（和） | 伊藤 浩之(東工大) / 柘植 政利(ソシオネクスト) / 廣瀬 哲也(神戸大) / 伊藤 靖朗(広島大) / 津邑 公暁(名工大) / 山口 基(ルネサスエレクトロニクス) |
| 幹事補佐氏名（英） | Hiroyuki Ito(Tokyo Inst. of Tech.) / Masatoshi Tsuge(Socionext) / Tetsuya Hirose(Kobe Univ.) / Yasuaki Ito(Hiroshima Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Motoi Yamaguchi(Renesas Electronics) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Integrated Circuits and Devices / Technical Committee on Computer Systems / Technical Committee on Circuits and Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | フローネットワークの辺負荷率平準化問題に対する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 |
| 第 1 著者 氏名（和/英） | 春日 輝 / Hikaru Kasuga |
| 第 1 著者 所属（和/英） | 創価大学(略称：創価大) Soka University(略称：Soka Univ.) |
| 第 2 著者 氏名（和/英） | 篠宮 紀彦 / Norihiko Shinomiya |
| 第 2 著者 所属（和/英） | 創価大学(略称：創価大) Soka University(略称：Soka Univ.) |
| 発表年月日 | 2018-12-23 |
| 資料番号 | CAS2018-111,ICD2018-95,CPSY2018-77 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | CAS-373,ICD-374,CPSY-375 |
| ページ範囲 | pp.131-135(CAS), pp.131-135(ICD), pp.131-135(CPSY), |
| ページ数 | 5 |
| 発行日 | 2018-12-14 (CAS, ICD, CPSY) |