Privacy-Preserving Bin-Packing With Differential Privacy

Tianyu Li*, Zekeriya Erkin, Reginald L. Lagendijk

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

95 Downloads (Pure)


With the emerging of e-commerce, package theft is at a high level: It is reported that 1.7 million packages are stolen or lost every day in the U.S. in 2020, which costs $25 million every day for the lost packages and the service. Information leakage during transportation is an important reason for theft since thieves can identify which truck is the target that contains the valuable products. In this paper, we address the privacy and security issues in bin-packing, which is an algorithm used in delivery centers to determine which packages should be loaded together to a certain truck. Data such as the weight of the packages is needed when assigning items into trucks, which can be called bins. However, the information is sensitive and can be used to identify the contents in the package. To provide security and privacy during bin-packing, we propose two different privacy-preserving data publishing methods. Both approaches use differential privacy (DP) to hide the existence of any specific package to prevent it from being identified by malicious users. The first approach combines differential privacy with k-anonymity, and the other one applies clustering before differential privacy. Our extensive analyses and experimental results clearly show that our proposed approaches have better privacy guarantees, better efficiency, and better performance than the existing works that use either differential privacy or k-anonymity.
Original languageEnglish
Article number9721160
Pages (from-to)94-106
Number of pages13
JournalIEEE Open Journal of Signal Processing
Publication statusPublished - 2022


  • Bin-packing
  • data anonymization
  • differential privacy
  • k-anonymity


Dive into the research topics of 'Privacy-Preserving Bin-Packing With Differential Privacy'. Together they form a unique fingerprint.

Cite this