講演名 | 2017-01-26 Edge Load Factor Balancing 問題と既知のNP完全問題との関連について 春日 輝(創価大), 山田 正史(創価大), 篠宮 紀彦(創価大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 本稿では,ネットワークフロー最適化問題の一つとして提案してきた Edge Load factor Balancing (ELB)問題に関して,既知のNP完全問題である Directed Two-commodity Integral Flow (DTIF)問題と対比させることによって性質を分析した.ELB問題は,あるネットワークにおいて,フロー量と辺の容量から定義される負荷率を平滑化するように各フローの経路を求める問題として定式化している.また,ELB問題に制限を与えた場合について,DTIF問題からの還元可能性と,複雑性クラスについて考察する. |
抄録(英) | This paper analyzes the property of Edge Load factor Balancing (ELB) problem, which is one of network flow optimization problems by comparing it with a well-known NP-complete problem, Directed Two-commodity Integral Flow (DTIF) problem. The ELB problem is formulated as a problem to find a set of paths that smooth edge load factor defined as the ratio of the amount of flows to a capacity of an edge. The complexity class of the restricted ELB problem is discussed based on the reducibility to the DTIF problem. |
キーワード(和) | ネットワークフロー / 負荷分散 / NP 困難 / グラフ理論 |
キーワード(英) | network flow / load balancing / NP-hard / graph theory |
資料番号 | CAS2016-83,ICTSSL2016-37 |
発行日 | 2017-01-19 (CAS, ICTSSL) |
研究会情報 | |
研究会 | CAS / ICTSSL |
---|---|
開催期間 | 2017/1/26(から2日開催) |
開催地(和) | 機械振興会館 |
開催地(英) | Kikai-Shinko-Kaikan Bldg. |
テーマ(和) | 学生セッション、一般 |
テーマ(英) | |
委員長氏名(和) | 高橋 俊彦(新潟大) / 岡田 和則(NICT) |
委員長氏名(英) | Toshihiko Takahashi(Niigata Univ.) / Kazunori Okada(NICT) |
副委員長氏名(和) | 平木 充(ルネサス エレクトロニクス) / 田村 裕(中大) / 中野 敬介(新潟大) |
副委員長氏名(英) | Mitsuru Hiraki(Renesas) / Hiroshi Tamura(Chuo Univ.) / Keisuke Nakano(Niigata Univ.) |
幹事氏名(和) | 越田 俊介(東北大) / 山口 基(ルネサスシステムデザイン) / 川上 博(NTTドコモ) / 井ノ口 宗成(静岡大) |
幹事氏名(英) | Shunsuke Koshita(Tohoku Univ.) / Motoi Yamaguchi(Renesas) / Hiroshi Kawakami(NTT DoCoMo) / Munenari Inoguchi(Shizuoka Univ.) |
幹事補佐氏名(和) | 橘 俊宏(湘南工科大) / 中村 洋平(日立) / 佐藤 翔輔(東北大) / 和田 友孝(関西大) |
幹事補佐氏名(英) | Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) / Shosuke Sato(Tohoku Univ.) / Tomotaka Wada(Kansai Univ.) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Circuits and Systems / Technical Committee on Information and Communication Technologies for Safe and Secure Life |
---|---|
本文の言語 | JPN |
タイトル(和) | Edge Load Factor Balancing 問題と既知のNP完全問題との関連について |
サブタイトル(和) | |
タイトル(英) | On Relevance between an Edge Load Factor Balancing Problem and the Conventional NP-complete Problems |
サブタイトル(和) | |
キーワード(1)(和/英) | ネットワークフロー / network flow |
キーワード(2)(和/英) | 負荷分散 / load balancing |
キーワード(3)(和/英) | NP 困難 / NP-hard |
キーワード(4)(和/英) | グラフ理論 / graph theory |
第 1 著者 氏名(和/英) | 春日 輝 / Hikaru Kasuga |
第 1 著者 所属(和/英) | 創価大学(略称:創価大) Soka University(略称:Soka Univ.) |
第 2 著者 氏名(和/英) | 山田 正史 / Masashi Yamada |
第 2 著者 所属(和/英) | 創価大学(略称:創価大) Soka University(略称:Soka Univ.) |
第 3 著者 氏名(和/英) | 篠宮 紀彦 / Norihiko Shinomiya |
第 3 著者 所属(和/英) | 創価大学(略称:創価大) Soka University(略称:Soka Univ.) |
発表年月日 | 2017-01-26 |
資料番号 | CAS2016-83,ICTSSL2016-37 |
巻番号(vol) | vol.116 |
号番号(no) | CAS-421,ICTSSL-422 |
ページ範囲 | pp.33-36(CAS), pp.33-36(ICTSSL), |
ページ数 | 4 |
発行日 | 2017-01-19 (CAS, ICTSSL) |