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.
Type de document :
Communication dans un congrès
David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Vijay Atluri; Günther Pernul; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 28th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2014, Vienna, Austria. Springer, Lecture Notes in Computer Science, LNCS-8566, pp.179-194, 2014, Data and Applications Security and Privacy XXVIII. 〈10.1007/978-3-662-43936-4_12〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01284854
Contributeur : Hal Ifip <>
Soumis le : mardi 8 mars 2016 - 11:06:24
Dernière modification le : jeudi 26 juillet 2018 - 14:08:02
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 10:17:20

Fichier

978-3-662-43936-4_12_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Yuan Hong, Jaideep Vaidya, Haibing Lu, Lingyu Wang. Collaboratively Solving the Traveling Salesman Problem with Limited Disclosure. David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Vijay Atluri; Günther Pernul; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 28th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2014, Vienna, Austria. Springer, Lecture Notes in Computer Science, LNCS-8566, pp.179-194, 2014, Data and Applications Security and Privacy XXVIII. 〈10.1007/978-3-662-43936-4_12〉. 〈hal-01284854〉

Partager

Métriques

Consultations de la notice

31

Téléchargements de fichiers

53