Solving Bin-packing Problems Under Privacy Preservation:Possibilities and Trade-offs

• 匿名处理方式会影响
• 优化方法也会影响

度量匿名化的质量

损失度量：

损失度量的下界函数：
（该函数为搜索树中节点的任何子树中的代价提供一个下界。我们使用下界函数）

匿名处理方式

1.全局重编码技术

最常用的全局重编码技术是全域泛化技术[49]。该方法的主要思想是在属性级别确定泛化级别。这意味着属于属性的所有值都被泛化到值泛化层次中的一个等价级别。

2.基于分区的一维重编码

假设区间可以划分为一组不相交的区间，而不是假定一个值泛化层次

感悟

这篇论文主要研究了如何将不同重量的物品打包到箱子里，以使使用的箱子数量最小化，同时包装的物品不会违反每个箱子的重量容量的问题，与众不同的是：
1.装箱优化问题的输入数据（物品的权重）是匿名的。

一种直接的优化方法是直接将匿名数据作为装箱问题的输入，这意味着我们可以直接使用泛化产生的下界。

但是，这种方法存在两个问题：（1）求解质量，即使用的箱数，可能会被高估或低估；（2） 这些解决方案可能是不可行的，因为可能会违反料仓的重量-容量约束。

这两个问题是由于这种直接的方法忽略了数据的不确定性，这是由值的泛化和抑制引起的。

这类数据不确定性的一种常用方法是robust优化[7]，其基本思想是确保每个权重的选择都有一个可行的解。问题可表达为

这种方法将区间的上界作为输出