私有近似处理：聚类与顶点覆盖问题的研究

聚类与顶点覆盖的私有近似Amos Beimel、Renen Hallak和Kobbi Nissim内盖夫本-古里安大学计算机科学系抽象。搜索问题的私人近似处理寻找搜索问题的近似解，同时尽可能少地披露信息。 本文的工作重点是研究顶点覆盖问题和两个聚类问题-k-在[Beimel，Carmi，Nissim和Weinreb，STOC，2006]中考虑了顶点覆盖，我们改进了他们的不可行性结果。聚类算法经常应用于敏感数据，因此在安全计算和私有近似的上下文中是感兴趣的。我们表明，这些问题不承认私人近似，甚至近似算法，泄漏显着数量的位。对于顶点覆盖问题，我们给出了一个严格的不可行性结果：每一个ρ（n）-逼近顶点覆盖的算法必须泄漏Ω（n/ρ（n））位（其中n是图中的顶点数）.对于聚类问题，我们证明了即使近似比很差的近似算法也必须泄漏Ω（n）位（其中n是实例中的点数）。对于这些结果，我们开发了新的证明技术，这是更简单和直观的比Beimel等人，并且还允许更强的不可行性结果。我们的证明依赖于Promise 问 题 的 难 度 ， 其 中 存 在 唯 一 的 最 优 解 [Valiant 和 Vazirani ，Theoretical Computer Science，1986]，NP-hard问题的近似证人的难度（[Kumar和 Sivakumar ，CCC ， 1999] 和 [Feige ，Langberg和 Nissim ，APPROX，2000]），以及简单的随机嵌入实例到更大的实例中。1介绍在安全多方计算中，两方或多方希望在不泄漏任何其他信息的情况下对他们的联合数据进行计算。通过[22，8，2]的一般可行性结果，这个任务被很好地定义并完全解决了多项式时间可计算函数。当各方希望计算的不是函数或计算不可行（或两者）时，不能直接应用可行性结果，并且在选择函数时必须特别小心，研究部分得到以色列科学基金会（第860/06号赠款）和弗兰克尔计算机科学中心的支持。部分研究是在第一和第三作者在加州大学洛杉矶分校纯粹与应用数学研究所时完成的。S.P. Vadhan（编辑）：TCC 2007，LNCS 4392，pp.383为2007年实现增长而进行的全面战略部署384A. 贝梅尔河Hallak和K.尼辛是安全计算的，因为安全计算的结果可能泄漏信息。我们处理这样的问题-近似算法不会泄漏比特定实例的解决方案集合更多的信息私人近似的概念首先在近似函数的背景下提出和研究[6，10]，最近被扩展到搜索问题[1]。这些作品还考虑放宽私人近似，允许有界泄漏。私有近似的研究产生了混合的结果：（i）私有近似算法或泄漏非常少的算法被提出用于充分研究的问题[6，10，7，15，13，1]，但是（ii）一些自然函数不允许私有近似，除非允许一些（小）泄漏[10];并且一些搜索问题甚至不允许具有显著泄漏的近似算法[1]。我们继续后面的研究路线，并证明顶点覆盖和两个聚类问题-k-甚至是泄漏大量比特的近似算法1.1以前的作品Feigenbaum等人。[6]指出，函数的近似可能会揭示实例上的信息，而这些信息不会被精确（或最佳）函数结果所揭示。因此，他们通过模拟范例制定了一个私有近似的概念，可以防止这种泄漏。它们的定义意味着，如果应用于实例x，y，使得f（x）= f（y），则应用于具有mf（x），f（y）的任意一个g的x ima t的结果是不可见的。根据私人近似的定义，Feigenbaum et al.提供了一个近似的协议具有通信复杂度的两个n位串的汉明距离操作系统（脚本），以及用于处理prox的polynmialsotingpermanen nnnenti n t int inher自然#P问题关于私有近似的后续工作将汉明距离的通信复杂度改进为polylog（n）[13]。其他关于特定函数的私有近似的工作包括[15，7]。试图构建某些NP完全问题的目标函数的私人近似是不成功的。Halevi、Krauthgamer、Kushilevitz和Nissim [10]解释了这一现象，证明了即使在近似比n1−n内计算最小顶点覆盖的大小也是强不可近似的结果。因此，他们提出了一种放松，允许输入的确定性谓词的泄漏。幸运的是，这种在隐私方面的轻微妥协允许对任何承认良好的确定性近似的问题进行相当好的近似。例如，最小顶点覆盖可以在4的比率内近似，仅泄漏一位近似。最近，Beimel，Carmi，Nissim和Weinreb [1]将[6]的隐私要求从函数扩展到搜索问题，给出了一个（看似）宽松的定义，只允许泄漏问题的所有精确解的集合所隐含的任何内容。稍微正式一点，如果应用于共享完全相同的（最优）解集的实例x，y，则近似的结果聚类与顶点覆盖385−AA·AA·在x上的算法（x）应该与（y）不可区分。 他们表明，即使在这个定义下，私下近似顶点覆盖和3SAT的搜索问题也是不可行的。采用[10]的松弛到私有搜索的上下文中，Beimel等人。对于max exact 3SAT，显示了一种近似算法，其近似比为7/ 8s，仅泄漏O（log logn）位。对于顶点覆盖，改进更为适度– 在比率ρ（n）内存在泄漏L（n）比特的近似算法，其中ρ（n）L（n）=2n。另一方面，他们证明了泄漏O（logn）位的顶点覆盖算法无法实现n次近似。我们把这个差距缩小到常数。Indyk和Woodru [13]在近邻搜索的背景下提出了私有近似的不同松弛，我们在第4节中提到了这种松弛的推广。1.2我们的贡献这项工作的主要部分研究如何私人逼近的概念和它的变种结合研究NP完全搜索问题– 顶点覆盖、k-中心和k-中值。对于这些问题，我们给出了强有力的不可行性结果，这些问题适用于比[1]更宽松的隐私定义-这只需要（x）无法区分（y）关于 x，y有相同的唯一解为了证明我们的结果，我们引入了新的强有力的技术来证明私人近似的不可行性，即使有许多位的泄漏。顶点覆盖。 如前所述，文献[1]研究了顶点覆盖私有近似的可行性. 他们的分析在不可行性和可行性结果之间留下了指数差距我们缩小了这一差距，并证明，除非RP = NP，否则任何泄漏至多l（n）比特信息且在近似比ρ（n）以内的近似算法都满足ρ（n）l（n）=Ω（n 这个结果与[1]中描述的结果相比是紧密的（直到常数因子）：对于每个常数s> 0，有一个n1−n-近似算法用于顶点覆盖，泄漏2 n个n比特。集群。聚类是将n个数据点划分为不相交的集合，以最小化与每个点集内的距离相关的成本目标的问题。聚类的变体是数据挖掘和机器学习以及模式识别、图像分析和生物信息学中许多研究的焦点。我们考虑两个变体：（i）k-中心，其中聚类的成本是一个点到其最近中心的最长距离;以及（ii）k-中值，其中成本是点到其最近中心的平均距离。这两个问题都是NP完全问题[12，14，18]。此外，我们考虑两个版本的每个问题，一个输出的中心和第二输出的坐标的解决方案的索引。对于私有算法，这两个版本是不等价的，因为可以从输出中学习不同的信息。我们证明，除非RP= NP，否则这些问题的索引版本的每个近似算法必须泄漏Ω（n）位，即使其近似比为386A. 贝梅尔河Hallak和K.尼辛≥一一一← AAA差如2聚（n）。由于有一个2-近似算法，泄漏最多n位（中心集的关联向量），我们的结果是紧到一个常数因子。类似的结果证明在完整版本的文件的坐标版本的这些问题（使用“扰动”属性的试图绕过不可能的结果，我们研究了Indyk和Woodru [13]的隐私定义的泛化，最初是在近邻搜索的背景下提出的。在修改后的定义中，允许近似算法将η-近似解的集合泄漏到给定η的实例中。我们考虑k-中心的坐标形式，证明了在此定义下对每个η2都存在一个私有2-近似，当η2时在此定义下不存在近似算法.新技术。我们不可行性证明的基本思想是假设对于某个NP完全问题存在一个有效的私有近似算法，并利用该算法有效地找到与该问题的NP困难性相矛盾的问题的最优解。具体地说，在我们的证明中，我们取一个NP完全问题的实例x，将其转换为一个新的实例x，一旦得到x的近似解，就执行y，然后从y，有效地重建x的最优解。因此，我们构造了一个卡普约简，从原来的NP完全问题的私人近似版本的问题。这应该与[1]中的减少进行比较，[1]中使用了许多调用，其中根据先前的答案自适应地选择输入。我们的技术与[1]的技术明显不同，非常直观，相当简单。主要的区别是，我们处理的承诺版本的顶点覆盖和聚类，其中存在一个唯一的最优解。这些问题在随机约简下也是NP难的[21]。分析私有近似算法如何在Promise问题的实例上操作，我们清楚地确定了一个困难的来源，试图创建这样一个算法-它，本质上，必须输出最优解。此外，证明不可行的结果的情况下，唯一的问题表明，私人近似的硬度源于我们试图近似的“功能”的情况下，给定一个实例的功能返回其唯一的最优解。因此，我们的不可能性结果是针对具有唯一解的输入，其中隐私要求甚至比[1]的定义更小为了得到我们最强的不可能性结果，我们使用Kumar和Sivakumar [16]以及Feige，Langberg和Nissim [5]的结果，对于许多NP完全问题，近似证明是NP困难的（也就是说，将证明和近似视为集合，我们要求它们的对称差很小）。这些结果嵌入了最优解的冗余编码，这样看到最优解的“噪声”版本就可以恢复它。在我们的不可行性证明中，我们假设存在一个近似算法来解决一些唯一的问题，并使用这个算法来找到一个接近最优解的解。因此，[16，5]的NP-硬度结果意味着，有效算法A不存在。聚类与顶点覆盖387一一AA.DAx，x，y−DAy，x，y. ≤，我们的最后一个技术是将一个实例简单随机嵌入到一个更大的实例中。让我们来证明这个想法的唯一顶点覆盖问题。在这种情况下，我们取一个图，多项式地添加许多孤立的顶点，然后随机置换顶点的名称。我们假设存在一个私有的顶点覆盖近似算法，并且我们在更大的实例上执行。我们表明，以很高的概率，从原始图中出现在输出的顶点是原始图的唯一顶点覆盖的顶点。这种现象背后的直觉是，根据隐私要求，必须对由名称的不同随机排列产生的许多实例给出相同的答案，因此，如果一个顶点在A的答案中，那么它很有可能对应于一个孤立的顶点。Organization. 第2节包含本文中使用的主要定义和基本背景。第三节给出了基于唯一k-中心的困难性的k-中心的指数形式的几乎私有算法的不可能性结果。第4节讨论了k-中心的坐标形式的私人近似的另一种定义，并给出了这种定义的可能性和不可能性结果。第5节描述了我们关于顶点覆盖的几乎私有算法的不可能性结果。最后，第6节讨论了我们工作中出现的一些问题。2预赛在本节中，我们给出了本文所需的定义和背景我们从[1]中私有搜索算法的定义开始。之后，我们讨论了我们关注的问题：聚类问题-k-然后，我们定义了一个简单的属性的基础指标，这将使我们能够提出我们的结果在一个度量独立的方式。最后，我们讨论了我们用来证明不可行性结果的两个工具：（1）唯一问题和简约约简的困难性，以及（2）错误校正约简。2.1搜索问题Beimel等人[1]定义了搜索算法关于某个底层隐私结构R <${0，1}<$× {0，1}<$的隐私性，R <${0，1}<$× {0，1}<$是一个关于实例的等价关系。不存在x∈R，y表示t∈x，y∈R。等式关系确定了哪些实例不应该被私有搜索算法A区分开定义1（私有搜索算法[1]）。R是一个隐私结构。一个概率多项式时间算法A是关于R的私有算法，如果对每个多项式时间算法D和每个正多项式p（·），对于任意yx，y ∈ { 0，1 }，有ex是tssomen0∈Nsuch ttx <$Ry和|X|为|y| ≥ n0PR[（（））= 1] Pr[（（））= 1]1P（|X|）其中的概率是随机选择A和D的概率。388A. 贝梅尔河Hallak和K.尼辛−对于每个搜索问题，相关的隐私结构在[1]中定义，其中两个输入是等价的，如果它们具有相同的最优解集。在2.2节中，我们给出了我们所考虑的问题的具体定义。我们还将使用定义1的宽松版本，它允许（有界的）lea kage。如果R是 R的 一个等价类，R的等价关系等于R上的一个等价关系，则R的等价关系是R上的一个等价关系。定义2（[1]）。R是一个隐私结构。概率多项式时间算法A相对于R最多泄漏l位，如果存在隐私结构R，使得（i）R是R的一个独立的定义，并且（ii）A是R的独 立的。2.2k-中心和k-中值聚类k-中心和k-中值聚类问题是研究得很好的问题，两者都是NP完全的[12，14，18]。在这两个问题中，输入是某个度量空间中的点的集合P和参数c。输出是P中c个点通过将每个点分配到其最近的中心（任意打破联系），将其划分为聚类。k-center和k-median之间的区别是在成本函数中：在k-center中，成本是P中一个点到其最近中心的最大距离;在k- median中，它是点到其最近中心的平均距离。对于私有算法，输出索引或坐标的选择可能是重要的（可以从每个学习不同的信息），因此我们定义了每个问题的两个版本。定义3（k-中心-输出指数（k -中心-I））。给定一个集合P={p1，...，p n}和参数c，返回c个聚类中心的索引I ={i1，. ，i c}，其最小化最大簇半径。定义4（k-中心-输出坐标（k -中心-C））。给定集合P = {p1，p2，.，pn}和参数c，返回c个聚类中心C = {pi1，...，p ic}，其最小化最大簇半径（CP）。1k-median-I和k-median-C问题的定义类似。定理1（[12，14，18]）. 在一般度量空间中，k-中心（k-median）是NP-困难的.此外，对于任意s> 0，在一般度量空间中求k -中心的（2s）-逼近问 题 是NP-困难的.证明（草图）：约简是从控制集。 给定一个图G=（V，E），将每个顶点v∈ V变换为一个点p ∈ P。每两个点[1]我们不考虑中心不需要是P中的点的问题。聚类与顶点覆盖389n−⊆⊆⊆⊆R一∈∈一--R||||设dist（p1，p2）= 1，如果（v1，v2）E，否则dist（p1，p2）= 2.当距离为1和2时，它们满足三角不等式。在G i中存在一个大小为c的支配集，并且在P中存在一个大小为c且成本为1的k -中心聚类（成本为n-c的k -中值聚类）。此外，在所构造的实例中，每个成本小于2的k-中心解的成本为1，这意味着k-中心的（2-s）-近似的对于k-中心[9，11]有一个贪婪2-近似算法：任意选择第一个中心，每次迭代选择其他c1个点，最大化到先前选择的中心的距离。我们将利用上述的减少，以及2-近似算法这个问题，在续集。接下来，我们定义与k-中心相关的隐私结构。 只有实例（P1，c1），（P2，c2）是P1=P2和c1=c2是等价的，只要它们满足以下条件：第五章. 设P1，P2为n个点的集合，Cn为决定聚类中心个数的参数.– 在关系k-中心-I下，如果对每个集合I=i1，.，i c的c个点索引，I最小化（P1，c）i的最大聚类半径，i最小化（P2，c）的最大聚类半径。– 在以下关系下，（P1，c）和（P2，c）是等价的k-中心-C如果(i) 对于每一个c个点的集合CP1，如果C最小化（P1，c）的最大聚类半径，则CP2最小化（P2，c）的最大聚类半径;同样地，（ii）对于每一个c个点的集合CP2，如果C最小化（P2，c）的最大聚类半径，则CP1最小化（P1，c）定义6（k -中心的私人近似）。一个随机化算法是k-中心I（分别为k-中心C）的一个私有ρ（n）-近似算法，如果：（i）该算法是k-中心的一个ρ（n）-近似算法，即对每个n点实例（P，c）- 一组c个点-使得解的期望聚类半径至多是（P，c）的最优解的半径的ρ（n）倍。(ii) A相对于R k-中心-I（相应地k-中心-C）是私有的。在[1]中，顶点覆盖的定义是类似的2.3距离度量空间在聚类问题的不可行性结果中，我们使用了度量空间的一个简单性质这使我们能够保持结果的一般性和度量独立性。人们应该意识到，集群问题可能有不同程度的困难，这取决于所使用的基本度量。我们的不可能性结果将表明，唯一k-中心和唯一k-中位数可能390A. 贝梅尔河Hallak和K.尼辛.Σ∈ME表示给定度量M=·P区∈ M，其中P={p1，.，p n}，运行如果这些问题存在私有算法，则可以在随机多项式时间内精确求解。当使用的度量空间的问题是NP-困难的，这意味着RP= NP。该属性指出，给定一个点集合，可以向其中添加“遥远”的新点定义7（可扩展度量）。设M是度量空间族。一个矩阵空间Mis（ρ.，m）-exp和bleifheexisanalgorithm在n，m的时间多项式中，以及M的描述，并输出度量M∈ P，其中P ∈ {p1，. ，pn，pn+1，... ，pn+m}，使得–对于任意yi，j∈[n]，且nd，dist∈（pi，pj）=dist（pi，pj）– 当di = maxi，j ∈ [ n ]（dist（pi，pj））时，di（pi，pj）≥ρd<，且di≤n+m和1≤j1/2，没有一个有效的算法能使输入图G和一个整数t（其中G有唯一的顶点覆盖，大小为t）返回一个集合S，S是δ-接近G的最小顶点覆盖.我们接下来描述唯一k中心的结果。定义9（接近唯一-k-中心的最优解）。 一个集合S是唯一k -中心的实例（P，c）的最优解的δ-接近，如果存在（P，c）的最优解I，使得|S Δ I| ≤（1 −δ）n。定理3. 如果RP=NP，那么，对于每个常数δ > 2/3，没有有效的算法，对于每个唯一的- k -中心的实例（P，c），找到一个接近（P，c）的最优解的集合δ-。同样的结果也适用于unique-k-median的实例。定理3的证明方法与文献[5]中的证明方法相似。证明在本文的完整版本中描述。3聚类的几乎私有近似的不可行性在本节中，我们证明了如果RP= NP，则聚类问题的每个近似算法都不是私有的（事实上，必须泄漏Ω（n）位）。我们将给出k-中心-I的完整处理（假设基础度量根据定义7是可扩展的）。所需的修改392A. 贝梅尔河Hallak和K.尼辛一一··∈/∈/∈≥··--·{}Rk-中心-I/∈··/∈AAk-median-i是小的。k-中心C和k-中值C的证明是不同的，并且使用度量的“可微扰”性质。后3个问题的证明出现在本文的完整版本中。我们将通过描述私有算法的不可行性结果来开始我们对k-中心-I的证明，然后我们考虑确定性几乎私有算法。随机几乎私有算法的不可行性结果出现在本文的完整版本3.1聚类问题在本节中，我们证明了k-中心I的私有近似算法的存在性意味着RP中唯一的-k-中心利用promise版本唯一k中心的硬度，我们得到了不可行结果.现在我们将证明，任何私有ρ（n）-近似算法必须本质上返回实例的唯一解中的所有点 我们利用了基本度量是（2 n ρ（n +1），1）-可扩展的事实。 给定实例（P，c）=（p1，...，pn，c）对于k-中心I，我们使用带有参数（2 n ρ（n+1），1）的算法E xpand通过添加E xpand返回的点p ∞来创建实例（P∞，c+1），即pn+1=p∞和dist_（pi，p∞）ρ（n+1）d. （P∞，c+1）的任何最优解都包含新的点p∞（如果p∞I∞，则此解的代价至少为2n ρ（n +1）d，而如果p ∞ I ∞，则代价至多为d）。因此，唯一的最优解I∞由（P，c）的最优解I加上点p ∞的指数n+1组成。引理2. 让是k -中心I的一个私人ρ（n）-近似算法，设（P，c）是k-中心-I的一个实例，并如上所述构造（P∈，c+1）。 然后Pr[A（P≠，c+1）返回（P，c）的所有临界点的指数] ≥ 1/3。概率是在算法A的随机硬币上取的。证据设p i1，. p ic是（P，c）的唯一最优解的点（因此p i1，...，其中pic，pn+1是（P ∈，c +1）的唯一最优解的点. 考虑一个例子（P，c +1），其中P与P相同，除了点p i1和p∞的索引（i i和n+1）交换。2由于p i1和p∞都是P中的最优解，交换它们不会改变最优解，因此（P，c +1）（P，c +1）。让我来解释一下，让我来解释一下，让我来解释一下，（P， c+1）和d（P=0， c+1）分别 注意，（P，c +1）的最优成本由d限定。 如果i1本文给出了一个2nρ（n+1）d的聚类算法。因此，如果Pr[i1I/（2n）算法不能保持ρ（n+1）的近似比。这意味着tPr[i1因此，在一般情况下，可以用Ω（1 /n）来区分（I<，P，P）与（I，P，P），从而在最短时间内产生一个p（I，P，P）。 对于索引i2，.，一个C。为了结束证明，我们使用并界并得到Pr[i1，...，ImI]≥1−2c/3n≥1/3。H[2]请注意，虽然PJ可以从P有效地构造出来，但PJJ的构造只是一个思想实验。聚类与顶点覆盖393≤一--一/≤现在我们得到了不可行性结果：定理4. 设ρ（n）为2poly（n）. k-中心-I问题不允许多项式时间私人ρ（n）-近似，除非唯一的k-中心可以在概率多项式时间内求解.证据设是k -中心I的多项式时间私人ρ（n）-逼近。令（P，c）=（p1，...，pn，c）是唯一k -中心的一个实例，I是其唯一解中中心的指数. 通过添加点pn+1 = p ∞，如上所述构造实例（P，c +1）。当ρ（n）≤2 poly （n ）时，用E-expand算法构造P算子是有效的.根据引理2，A（P）以至少1 / 3的概率包含I中的每个索引。 在高概率情况下，A（P <$，c +1）恰好包含来自P的c个点，并且集合A（P <$）\{n +1}是（P，c）的唯一最优解。H结合定理4和推论1，我们得到：推论2.设ρ（n）≤ 2poly（n）. k-中心-I问题（一般度量版本）不能在多项式时间内私下ρ（n）-近似，除非RP/= NP。3.2泄漏多比特的聚类问题的确定性近似的不可行性在这一节中，我们证明了即使RP = NP，对于每个ρ（n）2 poly（n），也不存在泄漏0的k -中心-I的有效确定性ρ（n）-近似算法。015n比特（如定义2中）。[3]与上一节一样，我们假设基础距离度量是可扩展的。为了证明k -中心-I的几乎私有近似的不可行性，我们假设存在一个有效的确定性ρ（n）-近似算法，它泄漏0. 015n比特。我们使用这个算法来找到一个接近唯一k中心实例的解的集合。在第3.1节中描述的私有算法的不可行性结果的证明中，我们从唯一-k-中心的实例P开始，并通过向P添加“远”点来生成新的实例P我们考虑了一个实例P，它等价于P，并认为，由于实例是等价的，一个决定性的私有算法必须在两个实例上返回相同的输出。对于几乎私有的算法，我们不能使用相同的证明。虽然实例P和P是等价的，但即使泄漏一个位的算法也可以在P和P上给出不同的答案。克服这个问题的第一个想法是线性添加许多新的因此，任何确定性近似算法必须返回所有“远”点和原始点的子集。然而，不能保证该子集是原始实例的最优解。第二个想法是使用实例索引的随机重命名我们将证明几乎私有算法的输出以很高的概率（在随机选择重命名的情况下）接近最优解[3]在这篇文章中，常数没有被优化。394A. 贝梅尔河Hallak和K.尼辛·\一一一→⊂def\一个联系我们··{}联系我们\n||||| ||− { ∈}|−⊆{∈}唯一的k中心。这与在2.5节中描述的NP困难相矛盾，即找到一个接近唯一k-中心实例的精确解的集合接下来我们正式定义添加“远”点和置换名称的构造。给定一个具有距离函数dist的唯一k-中心实例（P，c），利用带参数（2ρ（10n），9n）的E-EXPAND算法，通过添加9n个“远”点，生成一个具有距离函数dist的唯一k-中心实例（P，c设Nd=ef10n是P中点的个数，且dc=efc+9n. Wenextchooe一个置换π：[N] → [N]来创建一个新的实例（Pπ，9n+c），函数dist，其中dist（p， p）d=efdist（p， p）。πππ（i）π（j） i j我们从一些符号开始。设I是（P，c）和Sd=ef[n]的唯一最优解中 I（thatis，S是原始实例P中不在最优解中的点的索引的集合注意I= c，S = n c。对于任何集合A[N]，我们记为π（A）=π（i）：i A。Pπ和集合S、I的构造如图所示。1.一、很容易看出，（P π，cπ）的最优解I π包括9 n个“远”点，即，p π（i）：n+ 1我10 n（如果不是，则此解决方案的成本为至少2 ρ（N） d，如果 π（n+1），.，π（10 n） I π成本最多为d）。因此，I π恰好包含p π（i）：1in中的c个点，它必须是π（I）。也就是说，（P π，c π）的唯一最优解I π由[N] \π（S）中的指数组成。观察2. 设π1，π2是两个置换，使得π1（S）= π2（S）. 然后，（Pπ1，cπ）Rk-中心I （Pπ2，cπ）。在图2中，我们描述了算法C LOSETO U NIQUEk-C ENTER，该算法找到了一个接近唯一k -中心实例的唯一最小解的集合，假设存在k -中心-I的确定性ρ（N）-近似算法，该算法泄漏0。015N位。请注意，在该算法中，我们对（P π，cπ）执行近似算法-N = 10 n个点的实例-因此（及其泄漏）的近似比是N的函数。接下来我们证明，算法C以很高的概率输给UNI qUEk- CENTER返回一个接近最优解的集合。在分析中，我们将排列π：[N] [N]的集合划分为不相交的子集。我们证明 在每个子集中，算法C以很高的概率输给UNI qUEk。假设它选择了子集中的置换，则C enter返回接近最优解的集合。特别地，对于每个D[N]，我们考虑置换π的子集，使得π（S）=D。在其余的证明中，我们固定一个具有唯一最优解I和定义Sd=ef[n]的实例（P，cI. 对于更多的人，我们将设置D[N]sucthatD=S，并且仅考虑使得π（S）=D的置换。（该算法不需要知道S和D;这些集合用于分析。我们在引理4中证明了[N]（Pπ，cπ）以很高的概率接近D，并且我们在引理3中表明，在这种情况下，算法C输给 UNI qUEk-CENTER成功。聚类与顶点覆盖395一一| ∩| ≤π一算法C输给 U_ nq_UE_k-C_ENTER：Promise：（P，c）有一组唯一的c个聚类中心，最大聚类半径不超过t。输出：一组0.7-接近于c个聚类中心的唯一集合，最大聚类半径至多为t。输入：实例（P={p1，...，pn}，c）和整数t。1. 使用带有参数（2·ρ（10n），9n）的算法EXPAND创建一组点3. 设B <$A（Pπ，c +9 n）和B−1<${i ∈ [n]：π（i）∈ B}。2. 随机选择一个排列π：[N] → [N]，并构造Pπ。PJ={P1，...，pn，pn+1，...，p10n}。4. 返回B-1。SD=π（S）我[个π（I）点P点PπFig. 1. Pπ的构造图二. 一个算法，找到一个集合0.7-接近唯一的k-中心的一个实例的唯一最小解，假设这是一个几乎私人的近似算法，k-中心-I引理3. 设B是一个集合，使得B D0. 15 n和π是一个置换使得（P π，cπ）=B。然后，当算法C在步骤（2）中选择置换π时，算法C LOSETO UNIQUEk-C ENTER返回接近I的集合0.7。证据当选择π时，算法C输给 UNI qUEk-CENTER返回集合B−1= {i∈ [n]：π（i）∈B}= {i∈I：π（i）∈B}<${i∈S：π（i）∈B}={i ∈ I：π（i）∈ B}<${i：π（i）∈ B <$D}。我们，|B−1\I|为|BD|≤0。15N。 As|B−1|为|我|，weget|I\B−1|为|B−1\I|≤0的情况。15N。在那里，|B−1ΔI|≤0。3n，ndB−1是0。七点接近。H4.我爱你 Letprd=efPr[|A（P，c）D|≤0。15n]，当您获得预充能力时，在π服从π（S）= D的条件下，则pr ≥ 3/4。证据 我们证明了，如果pr = 3/ 4，则存在一个置换π，使得< 不是（Pπ，cπ）上的ρ（N）-近似k-中心-I，这与A的定义相矛盾。396A. 贝梅尔河Hallak和K.尼辛e一.Σ一联系我们··A {≤ ≤}一| |− ||−|∩|一RABB使得π（S）=D且A（Pπ，c）=B至多为（n-c）！0n（0. 15n）！c）！. 首先，0nH ≤ 2 H（0. 15）n≤（16）0。15n，其中H（0. 15）≤ 0. 61号是香农二、n.15N在这个证明中，我们说一个集合B是“坏”的，如果BD> 0。15N。使π（S）=D的排列数是（S）！（N S）！=（n c）！（9 n+c）！当我们假设pr为<3/4时，使得π（S）= D且A（P π，cπ）是“坏”的排列π的数目至少为0的情况。25（n-c）！（9 n+c）！≥（n-c）！卢恩9n+c9n+c。（一）我们将证明，由性质，这种排列的数量是小得多，实现了矛盾，我们的假设，pr 3/ 4。<我们首先上界，对于给定的 π使得π（S）=D且（Pπ，cπ）=B。请注意，决定性算法（Pπ，cπ）的输出必须包含pπ（i）：n+1i10n（否则近似解的半径至少为2ρ（N）d，当取pπ（i）中的所有点时，至多为d）：n+ 1i10n和另外的c点）。因此，如果置换π满足π（S）=D和A（Pπ，c）=B，则[N] \B<$D<$π（I），这意味着[N] \（B<$D）<$π（I）。记bd=ef|BD|≥0。15n，|= N −| B |− |D|+的|BD|= 10n −（9n + c）−（n-c）+ b = b。|= 10 n − (9 n + c) −(n − c)+ b = b.每个满足π（S）=D和（Pπ，cπ）=B的置换π都有一个大小为b的固定集合包含在π（I）中，因此，这样的置换的数目至多（|S|）！.|快！|Σb! （N−|S| −b）！ =（n-c）！.cb！（9n+c−b）！.取b= 0。15 n只能增加这个表达式（因为我们要求在π（I）中包含更小的集合）。 我们，不是在g中有c≤n，是nu。mberoofpermutatio ns.15N熵因此，使用斯特林近似，这种排列为至多O. √n（0.（3）0. 15N·你知道吗？（n-c）！卢恩. 9 n + ce.（二）通过观察2，使得π（S）= D的置换π的所有实例（P π，cπ）根据k-中心-I是等价的。因此，由于泄漏最多为0。015 N比特，最多有2个0。在这些情况下，N个可能的答案，特别地，最多有2个0。015N=2 0。15n因此，通过（2），使得π（S）=D并且A（P π，cπ）是“ 坏 ” 集 合 的 排 列 的 数 目 至 多 是. 0 15√0 15 - 是的O聚类与顶点覆盖397n（0.n ·n- 是的9 n + ce由于（3）中的排列数小于（1）中的排列数，我们得出结论：pr≥ 3/ 4。H（n-c）！（398A. 贝梅尔河Hallak和K.尼辛一不超过ηRLk-中心-C//结合引理3和引理4，如果是k -中心-I的ρ（N）-近似算法，则泄漏0。015N比特，则算法C输给 U_ nq_UE_k。C_ENTER返回一个集合，该集合以至少3/ 4的概率接近最优解，并且根据定理3，这是不可能的，除非RP= NP。在本文的完整版本中，我们证明了算法C输给了 UNI qUEk-C输入找到一个接近最优解的集合，即使A是随机的。定理5. 设ρ（n）为2poly（n）.如果RP = NP，则k -中心I的每个有效ρ（n）-近似算法（在一般度量版本中）必须泄漏Ω（n）个比特。4关于[13]为了绕过不可能的结果，我们研究了Indyk和Woodru [13]的定义的推广，最初是在近邻搜索的背景下提出的。在修改后的定义中，允许近似算法将近似解的集合泄漏到实例中。更正式地说，我们使用定义1，并设置等价关系η以包括η-近似解：10. carton 设L是一个具有代价函数代价的极小化问题. 如果cost x（w）≤η· min w'（cost x（w≠）），则解w是x的η-逼近。让appx（x）d=ef{w：wisan n n-approximationforx}。定义对等网络RL如下：x<$Rηyi<$appx（x）=appx（y）。请注意，定义10产生了一系列等价关系，由η参数化。当η=1时，我们得到与前面相同的等价关系我们考虑k-中心的坐标形式.在本文的完整版本中，我们给出了k-中心-C在η=2时的阈值：（1）当η≥ 2时，每个近似算法相对于Rη. (2)对于η2，这个问题和η=1时一样难。5泄漏信息在[1]中，证明了如果RP = NP，则对每个常数s> 0，每个n1−n逼近顶点覆盖的算法必定泄漏Ω（log n）位. 在本文中，我们加强了这个结果，表明如果RP = NP，那么每个n1− n-近似顶点覆盖的算法必须泄漏Ω（n <$）位。 我们注意到这个结果几乎是紧的：在[1]中，描述了一个n1−n-近似顶点覆盖并泄漏2n个n比特的算法。我们将分阶段描述不可行性结果我们将首先描述顶点覆盖的确定性私有近似的不可行性的一个新证明，然后我们将描述顶点覆盖的确定性n1−n-近似的不可行性，它最多泄漏αn个比特（其中α<1是一个特定的常数）。在完整版本的文件中，我们显示了相同的不可行性结果的随机算法。聚类与顶点覆盖399−{∈}→//| |5.1点覆盖的确定性私有逼近的不可行性我们假设存在一个确定