Paper Abstract and Keywords |
Presentation |
2021-03-15 11:10
Approximate solution of the communication link load balancing problem using the lagrangian relaxation method Daichi Shimizu, Fumiya Onogi, Norihiko Shinomiya (Soka Univ) MSS2020-44 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
This study has focused on the UELB problem that aims at leveling the traffic load of a communication link in an information network by determining the path of a flow that minimizes the maximum load factor of the link. The UELB problem has been proved to be NP-hard, and an approximate solution method using the LP relaxation has been proposed to verify the results. This paper proposes another algorithm using the Lagrangian relaxation method in order to objectively evaluate the accuracy of the approximate solutions obtained so far. We have conducted comparison experiments with the method using LP relaxation. The result has demonstrated that the proposed algorithm has relatively higher computational complexity and taken a long time to calculate the solution because of using the subgradient method for the Lagrangian relaxation. In addition, the weakened constraints lead to resulting in a high traffic load factor, which indicates that the conventional LP relaxation is more effective. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
Network flow problem / Lagrangian relaxation method / Subgradient method / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 120, no. 429, MSS2020-44, pp. 5-9, March 2021. |
Paper # |
MSS2020-44 |
Date of Issue |
2021-03-08 (MSS) |
ISSN |
Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
MSS2020-44 |
Conference Information |
Committee |
NLP MSS |
Conference Date |
2021-03-15 - 2021-03-16 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Online |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
MSS, NLP, Work In Progress (MSS only), and etc. |
Paper Information |
Registration To |
MSS |
Conference Code |
2021-03-NLP-MSS |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Approximate solution of the communication link load balancing problem using the lagrangian relaxation method |
Sub Title (in English) |
|
Keyword(1) |
Network flow problem |
Keyword(2) |
Lagrangian relaxation method |
Keyword(3) |
Subgradient method |
Keyword(4) |
|
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Daichi Shimizu |
1st Author's Affiliation |
Soka University (Soka Univ) |
2nd Author's Name |
Fumiya Onogi |
2nd Author's Affiliation |
Soka University (Soka Univ) |
3rd Author's Name |
Norihiko Shinomiya |
3rd Author's Affiliation |
Soka University (Soka Univ) |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2021-03-15 11:10:00 |
Presentation Time |
25 minutes |
Registration for |
MSS |
Paper # |
MSS2020-44 |
Volume (vol) |
vol.120 |
Number (no) |
no.429 |
Page |
pp.5-9 |
#Pages |
5 |
Date of Issue |
2021-03-08 (MSS) |
|