| Presentation | 2006-07-21 Secure optimization of Traveling Salesman Problem using Scalar Product Comparison Protocol Jun SAKUMA, Shigenobu KOBAYASHI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We propose a secure local search protocol for the distributed combinatorial optimization problem. In the distributed combinatorial optimization problem, information regarding the cost function is distributed among multi parties. In distributed Traveling Salesman Problem (TSP), traveling costs between any two cities and city sets to be visited are distributed and private. Distributed TSP can be securely solved by secure local search based on private scalar product comparision protocol without revealing distributed information. The time complexity of our protocol is O(n^2) in preparation phase where n is the number of cities but the computation time is kept O(1) per one iteration. The waiting time required to complete the optimization is reasonable even when the city-size is more than a thousand and the optimization is processed without sharing the distributed information. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Multi-party protocol / privacy / optimization / scalar product comparison / TSP / supply chain management |
| Paper # | ISEC2006-45 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2006/7/14(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Secure optimization of Traveling Salesman Problem using Scalar Product Comparison Protocol |
| Sub Title (in English) | |
| Keyword(1) | Multi-party protocol |
| Keyword(2) | privacy |
| Keyword(3) | optimization |
| Keyword(4) | scalar product comparison |
| Keyword(5) | TSP |
| Keyword(6) | supply chain management |
| 1st Author's Name | Jun SAKUMA |
| 1st Author's Affiliation | Department of Computational Ingelligence and Systems Science() |
| 2nd Author's Name | Shigenobu KOBAYASHI |
| 2nd Author's Affiliation | Department of Computational Ingelligence and Systems Science |
| Date | 2006-07-21 |
| Paper # | ISEC2006-45 |
| Volume (vol) | vol.106 |
| Number (no) | 176 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |