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
Contributor : Hal Ifip Connect in order to contact the contributor
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


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads