Presentation | 2018-12-23 An approximation algorithm with LP rounding for an unsplittable flow edge load factor balancing problem in a flow network Hikaru Kasuga, Norihiko Shinomiya, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | distributed management network / network flow problem / load balancing / LP rounding |
Paper # | CAS2018-111,ICD2018-95,CPSY2018-77 |
Date of Issue | 2018-12-14 (CAS, ICD, CPSY) |
Conference Information | |
Committee | ICD / CPSY / CAS |
---|---|
Conference Date | 2018/12/21(3days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Hideto Hidaka(Renesas) / Koji Nakano(Hiroshima Univ.) / Hideaki Okazaki(Shonan Inst. of Tech.) |
Vice Chair | Makoto Nagata(Kobe Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) / Taizo Yamawaki(Hitachi) |
Secretary | Makoto Nagata(Panasonic) / Hidetsugu Irie(Tohoku Univ.) / Takashi Miyoshi(Utsunomiya Univ.) / Taizo Yamawaki(Hokkaido Univ.) |
Assistant | 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) |
Paper Information | |
Registration To | Technical Committee on Integrated Circuits and Devices / Technical Committee on Computer Systems / Technical Committee on Circuits and Systems |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | An approximation algorithm with LP rounding for an unsplittable flow edge load factor balancing problem in a flow network |
Sub Title (in English) | |
Keyword(1) | distributed management network |
Keyword(2) | network flow problem |
Keyword(3) | load balancing |
Keyword(4) | LP rounding |
1st Author's Name | Hikaru Kasuga |
1st Author's Affiliation | Soka University(Soka Univ.) |
2nd Author's Name | Norihiko Shinomiya |
2nd Author's Affiliation | Soka University(Soka Univ.) |
Date | 2018-12-23 |
Paper # | CAS2018-111,ICD2018-95,CPSY2018-77 |
Volume (vol) | vol.118 |
Number (no) | CAS-373,ICD-374,CPSY-375 |
Page | pp.pp.131-135(CAS), pp.131-135(ICD), pp.131-135(CPSY), |
#Pages | 5 |
Date of Issue | 2018-12-14 (CAS, ICD, CPSY) |