摘要翻译：
引入并研究了一个新的优化问题&超顶点覆盖问题。这个问题是标准顶点覆盖在超图中的推广：一个问题是寻找一个粒子的结构，其密度最小，使得超图的每个超边至少包含一个粒子。它也可以用于重要的实际任务，如组测试过程中，人们希望通过池测试来检测一个大组中的缺陷项目。利用基于空腔方法的统计力学方法，研究了随机regualr超图情形下HVC问题的相图。根据变量的取值和测试程度的不同，可能会出现不同的情况：HVC问题可能处于复制对称阶段，也可能处于复制对称一步破缺阶段。在这两种情况下，我们给出了粒子最小密度和相空间结构的显式结果。因此，在某种意义上，这些问题比原始顶点复盖问题简单，在原始顶点复盖问题中，到目前为止，由于需要完全复制品对称性破缺而阻止了精确结果的推导。最后，我们证明了基于信念传播的抽取过程和调查传播算法为解决大个体的超顶点覆盖问题提供了非常有效的策略。
---
英文标题：
《Statistical Mechanics of the Hyper Vertex Cover Problem》
---
作者：
M. M\'ezard, M. Tarzia
---
最新提交年份：
2007
---
分类信息：

一级分类：Physics        物理学
二级分类：Statistical Mechanics        统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
一级分类：Physics        物理学
二级分类：Disordered Systems and Neural Networks        无序系统与神经网络
分类描述：Glasses and spin glasses; properties of random, aperiodic and quasiperiodic systems; transport in disordered media; localization; phenomena mediated by defects and disorder; neural networks
眼镜和旋转眼镜；随机、非周期和准周期系统的性质；无序介质中的传输；本地化；由缺陷和无序介导的现象；神经网络
--

---
英文摘要：
  We introduce and study a new optimization problem called Hyper Vertex Cover. This problem is a generalization of the standard vertex cover to hypergraphs: one seeks a configuration of particles with minimal density such that every hyperedge of the hypergraph contains at least one particle. It can also be used in important practical tasks, such as the Group Testing procedures where one wants to detect defective items in a large group by pool testing. Using a Statistical Mechanics approach based on the cavity method, we study the phase diagram of the HVC problem, in the case of random regualr hypergraphs. Depending on the values of the variables and tests degrees different situations can occur: The HVC problem can be either in a replica symmetric phase, or in a one-step replica symmetry breaking one. In these two cases, we give explicit results on the minimal density of particles, and the structure of the phase space. These problems are thus in some sense simpler than the original vertex cover problem, where the need for a full replica symmetry breaking has prevented the derivation of exact results so far. Finally, we show that decimation procedures based on the belief propagation and the survey propagation algorithms provide very efficient strategies to solve large individual instances of the hyper vertex cover problem.
---
PDF链接：
https://arxiv.org/pdf/707.0189