Skip to Main content Skip to Navigation
Conference papers

Collaboratively Solving the Traveling Salesman Problem with Limited Disclosure

Abstract : With increasing resource constraints, optimization is necessary to make the best use of scarce resources. Given the ubiquitous connectivity and availability of information, collaborative optimization problems can be formulated by different parties to jointly optimize their operations. However, this cannot usually be done without restraint since privacy/security concerns often inhibit the complete sharing of proprietary information. The field of privacy-preserving optimization studies how collaborative optimization can be performed with limited disclosure. In this paper, we develop privacy-preserving solutions for collaboratively solving the traveling salesman problem (TSP), a fundamental combinatorial optimization problem with applications in diverse fields such as planning, logistics and production. We propose a secure and efficient protocol for multiple participants to formulate and solve such a problem without sharing any private information. We formally prove the protocol security under the rigorous definition of secure multiparty computation (SMC), and demonstrate its effectiveness with experimental results using real data.
Document type :
Conference papers
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-01284854
Contributor : Hal Ifip <>
Submitted on : Tuesday, March 8, 2016 - 11:06:24 AM
Last modification on : Tuesday, August 13, 2019 - 11:32:01 AM
Long-term archiving on: : Sunday, November 13, 2016 - 10:17:20 AM

File

978-3-662-43936-4_12_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Yuan Hong, Jaideep Vaidya, Haibing Lu, Lingyu Wang. Collaboratively Solving the Traveling Salesman Problem with Limited Disclosure. 28th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2014, Vienna, Austria. pp.179-194, ⟨10.1007/978-3-662-43936-4_12⟩. ⟨hal-01284854⟩

Share

Metrics

Record views

104

Files downloads

638