| Presentation | 2019-01-18 Minimum p-Median Problem for Incomplete Networks Sho Tsugawa, Hiroyuki Ohsaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The minimum $p$-median problem is a combinatorial optimization problem finding a set of $p$ nodes in a network to minimize the weighted distance between each node and the nearest node in the median set. This paper formulates a generalization of the well known minimum $p$-median problem. Our problem aims to find the $p$-median set only from the incomplete information on the network. Studying this problem is motivated by the fact that it is difficult to accurately obtain the entire structure of real complex networks. This paper provides a simple heuristic algorithm for the minimum $p$-median problem for incomplete networks, and examines its effectiveness through experiments. Our results show that the formulated problem can be effectively solved by the heuristic algorithm even with a partial network constructed from a 10% node sampling. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | minimum $p$-median problem / network sampling / combinatorial optimization |
| Paper # | CQ2018-85 |
| Date of Issue | 2019-01-10 (CQ) |
| Conference Information | |
| Committee | CQ |
|---|---|
| Conference Date | 2019/1/17(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Tokyo Metropolitan Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Video/Voice Services Quality, Media Quality, Network Quality and QoS Control, Networks and Communications at Disaster, User Behavior, Machine Learning, etc. |
| Chair | Takanori Hayashi(Hiroshima Inst. of Tech.) |
| Vice Chair | Hideyuki Shimonishi(NEC) / Jun Okamoto(NTT) |
| Secretary | Hideyuki Shimonishi(NTT) / Jun Okamoto(Nippon Inst. of Tech.) |
| Assistant | Chikara Sasaki(KDDI Research) / Yoshiaki Nishikawa(NEC) / Ryo Yamamoto(UEC) |
| Paper Information | |
| Registration To | Technical Committee on Communication Quality |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Minimum p-Median Problem for Incomplete Networks |
| Sub Title (in English) | A Formulation and Experimental Evaluation |
| Keyword(1) | minimum $p$-median problem |
| Keyword(2) | network sampling |
| Keyword(3) | combinatorial optimization |
| 1st Author's Name | Sho Tsugawa |
| 1st Author's Affiliation | University of Tsukuba(Univ. of Tsukuba) |
| 2nd Author's Name | Hiroyuki Ohsaki |
| 2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| Date | 2019-01-18 |
| Paper # | CQ2018-85 |
| Volume (vol) | vol.118 |
| Number (no) | CQ-395 |
| Page | pp.pp.53-58(CQ), |
| #Pages | 6 |
| Date of Issue | 2019-01-10 (CQ) |