| 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) |