Solving bin-packing problems under privacy preservation: possibilities and trade-offs

Rowan Hoogervorst (Corresponding author), Yingqian Zhang, Gamze Tillem, Zekeriya Erkin, Sicco Verwer

Research output: Contribution to journalArticleAcademicpeer-review

44 Downloads (Pure)

Abstract

We investigate the trade-off between privacy and solution quality that occurs when a k-anonymized database is used as input to the bin-packing optimization problem. To investigate the impact of the chosen anonymization method on this trade-off, we consider two recoding methods for k-anonymity: full-domain generalization and partition-based single-dimensional recoding. To deal with the uncertainty created by anonymization in the bin-packing problem, we utilize stochastic programming and robust optimization methods. Our computational results show that the trade-off is strongly dependent on both the anonymization and optimization method. On the anonymization side, we see that using single dimensional recoding leads to significantly better solution quality than using full domain generalization. On the optimization side, we see that using stochastic programming, where we use the multiset of values in an equivalence class, considerably improves the solutions. While publishing these multisets makes the database more vulnerable to a table linkage attack, we argue that it is up to the data publisher to reason if such a loss of anonymization weighs up to the increase in optimization performance.
Original languageEnglish
Pages (from-to)203-216
Number of pages14
JournalInformation Sciences
Volume500
DOIs
Publication statusPublished - 1 Oct 2019

Fingerprint

Privacy Preservation
Bin Packing Problem
Bins
Stochastic Programming
Trade-offs
Multiset
Optimization Methods
Stochastic programming
K-anonymity
Bin Packing
Robust Optimization
Performance Optimization
Packing Problem
Robust Methods
Equivalence class
Linkage
Privacy
Computational Results
Table
Equivalence classes

Keywords

  • Bin-packing
  • Data anonymization
  • k-anonymity
  • Robust optimization
  • Stochastic programming

Cite this

Hoogervorst, Rowan ; Zhang, Yingqian ; Tillem, Gamze ; Erkin, Zekeriya ; Verwer, Sicco. / Solving bin-packing problems under privacy preservation: possibilities and trade-offs. In: Information Sciences. 2019 ; Vol. 500. pp. 203-216.
@article{aa9e19f50215453ab557f9a8724c97b5,
title = "Solving bin-packing problems under privacy preservation: possibilities and trade-offs",
abstract = "We investigate the trade-off between privacy and solution quality that occurs when a k-anonymized database is used as input to the bin-packing optimization problem. To investigate the impact of the chosen anonymization method on this trade-off, we consider two recoding methods for k-anonymity: full-domain generalization and partition-based single-dimensional recoding. To deal with the uncertainty created by anonymization in the bin-packing problem, we utilize stochastic programming and robust optimization methods. Our computational results show that the trade-off is strongly dependent on both the anonymization and optimization method. On the anonymization side, we see that using single dimensional recoding leads to significantly better solution quality than using full domain generalization. On the optimization side, we see that using stochastic programming, where we use the multiset of values in an equivalence class, considerably improves the solutions. While publishing these multisets makes the database more vulnerable to a table linkage attack, we argue that it is up to the data publisher to reason if such a loss of anonymization weighs up to the increase in optimization performance.",
keywords = "Bin-packing, Data anonymization, k-anonymity, Robust optimization, Stochastic programming",
author = "Rowan Hoogervorst and Yingqian Zhang and Gamze Tillem and Zekeriya Erkin and Sicco Verwer",
year = "2019",
month = "10",
day = "1",
doi = "10.1016/j.ins.2019.05.011",
language = "English",
volume = "500",
pages = "203--216",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier",

}

Solving bin-packing problems under privacy preservation: possibilities and trade-offs. / Hoogervorst, Rowan (Corresponding author); Zhang, Yingqian; Tillem, Gamze; Erkin, Zekeriya; Verwer, Sicco.

In: Information Sciences, Vol. 500, 01.10.2019, p. 203-216.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Solving bin-packing problems under privacy preservation: possibilities and trade-offs

AU - Hoogervorst, Rowan

AU - Zhang, Yingqian

AU - Tillem, Gamze

AU - Erkin, Zekeriya

AU - Verwer, Sicco

PY - 2019/10/1

Y1 - 2019/10/1

N2 - We investigate the trade-off between privacy and solution quality that occurs when a k-anonymized database is used as input to the bin-packing optimization problem. To investigate the impact of the chosen anonymization method on this trade-off, we consider two recoding methods for k-anonymity: full-domain generalization and partition-based single-dimensional recoding. To deal with the uncertainty created by anonymization in the bin-packing problem, we utilize stochastic programming and robust optimization methods. Our computational results show that the trade-off is strongly dependent on both the anonymization and optimization method. On the anonymization side, we see that using single dimensional recoding leads to significantly better solution quality than using full domain generalization. On the optimization side, we see that using stochastic programming, where we use the multiset of values in an equivalence class, considerably improves the solutions. While publishing these multisets makes the database more vulnerable to a table linkage attack, we argue that it is up to the data publisher to reason if such a loss of anonymization weighs up to the increase in optimization performance.

AB - We investigate the trade-off between privacy and solution quality that occurs when a k-anonymized database is used as input to the bin-packing optimization problem. To investigate the impact of the chosen anonymization method on this trade-off, we consider two recoding methods for k-anonymity: full-domain generalization and partition-based single-dimensional recoding. To deal with the uncertainty created by anonymization in the bin-packing problem, we utilize stochastic programming and robust optimization methods. Our computational results show that the trade-off is strongly dependent on both the anonymization and optimization method. On the anonymization side, we see that using single dimensional recoding leads to significantly better solution quality than using full domain generalization. On the optimization side, we see that using stochastic programming, where we use the multiset of values in an equivalence class, considerably improves the solutions. While publishing these multisets makes the database more vulnerable to a table linkage attack, we argue that it is up to the data publisher to reason if such a loss of anonymization weighs up to the increase in optimization performance.

KW - Bin-packing

KW - Data anonymization

KW - k-anonymity

KW - Robust optimization

KW - Stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=85066619466&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2019.05.011

DO - 10.1016/j.ins.2019.05.011

M3 - Article

AN - SCOPUS:85066619466

VL - 500

SP - 203

EP - 216

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

ER -