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

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

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.
TaalEngels
Pagina's203-216
Aantal pagina's14
TijdschriftInformation Sciences
Volume500
DOI's
StatusGepubliceerd - 1 okt 2019

Vingerafdruk

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

Trefwoorden

    Citeer dit

    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. blz. 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, blz. 203-216.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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

    VL - 500

    SP - 203

    EP - 216

    JO - Information Sciences

    T2 - Information Sciences

    JF - Information Sciences

    SN - 0020-0255

    ER -

    Hoogervorst R, Zhang Y, Tillem G, Erkin Z, Verwer S. Solving bin-packing problems under privacy preservation: possibilities and trade-offs. Information Sciences. 2019 okt 1;500:203-216. Beschikbaar vanaf, DOI: 10.1016/j.ins.2019.05.011