小边概率条件下较小植入团的算法

doi:10.16183/j.cnki.jsjtu.2017.10.008

摘要/Abstract

摘要： 针对植入团问题是平均情况复杂性理论的一个中心问题，将带植入团的随机图模型进行推广，提出小边概率条件，使得边概率可以随着顶点数目的增大而变小.使用随机算法分析中的概率工具，改进文献中算法的分析，证明在小边概率条件下，存在以很大概率找到推广模型中较小的植入团的多项式时间随机算法.

关键词: , 随机图, 植入团, 小边概率条件, 随机算法, 平均情况复杂性

Abstract: Planted clique problem is a central problem in averagecase complexity theory. The random graph with planted clique model is extended, and small edge probability conditions are invented to allow the edge probability to decrease. It is shown that under such conditions there exists a polynomialtime randomized algorithm to find a relatively small planted clique by using probability tools for analysis of randomized algorithms. The result improves analysis of the algorithm in the literature.

Key words: , random graph, planted clique, small edge probability, randomized algorithm, average case complexity

中图分类号:

TP 301.6

黄炫圭. 小边概率条件下较小植入团的算法[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1202-1206.

HUANG Xuangui. Algorithm for Relatively Small Planted Clique with
Small Edge Probability[J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1202-1206.

参考文献

［1］HASTAD J. Clique is hard to approximate within n1－ε［C］∥Proceedings of The 37th Annual Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 1996: 627636.
［2］JANSON S, LUCZAK T, RUCINSKI A. Random graphs［M］. New York: John Wiley & Sons, 2000.
［3］ARORA S, BARAK B. Computational complexity: A modern approach［M］. New York: Cambridge University Press, 2009: 361372.
［4］KARP R M. The probabilistic analysis of some combinatorial search algorithms［C］∥Algorithms and Complexity: New Directions and Recent Results. New York: Academic Press, 1976: 119.
［5］JERRUM M. Large cliques elude the Metropolis process［J］. Random Structures and Algorithms, 1992, 3(4): 347359.
［6］KUERA L. Expected complexity of graph partitioning problems［J］. Discrete Applied Mathematics, 1995, 57(2): 193212.
［7］ALON N, KRIVELEVICH M, SUDAKOV B. Finding a large hidden clique in a random graph［J］. Random Structures and Algorithms, 1998, 13(3/4): 457466.
［8］FEIGE U, RON D. Finding hidden cliques in linear time［C］∥Proceedings of The 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms. Nancy, France: Discrete Mathematics and Theoretical Computer Science (DMTCS), 2010: 189204.
［9］DEKEL Y, GURELGUREVICH O, PERES Y. Finding hidden cliques in linear time with high probability［C］∥Proceedings of the Meeting on Analytic Algorithmics and Combinatorics. San Francisco: Society for Industrial and Applied Mathematics, 2011: 6775.
［10］AMES B P W, VAVASIS S A. Nuclear norm minimization for the planted clique and biclique problems［J］. Mathematical Programming, 2011, 129(1): 6989.
［11］DESHPANDE Y, MONTANARI A. Finding hidden cliques of size N/e in nearly linear time［J］. Foundations of Computational Mathematics, 2015, 15(4): 10691128.
［12］FELDMAN V, GRIGORESCU E, REYZIN L, et al. Statistical algorithms and a lower bound for detecting planted cliques［C］∥Proceedings of The 45th Annual ACM Symposium on Theory of Computing. Palo Alto, USA: Association for Computing Machinery, 2013: 655664.
［13］MEKA R, POTECHIN A, WIGDERSON A. Sumofsquares lower bounds for planted clique［C］∥Proceedings of the 47th Annual ACM Symposium on Theory of Computing. Portland, USA: Association for Computing Machinery, 2015: 8796.
［14］DESHPANDE Y, MONTANARI A. Improved sumofsquares lower bounds for hidden clique and hidden submatrix problems［C］∥Proceedings of The 28th Conference on Learning Theory. Paris, France: JMLR, Inc, 2015: 523562.
［15］HAZAN E, KRAUTHGAMER R. How hard is it to approximate the best Nash equilibrium?［J］. SIAM Journal on Computing, 2011, 40(1): 7991.
［16］SANTHANAM R. The complexity of explicit constructions［J］. Theory of Computing Systems, 2012, 51(3): 297312.
［17］HAJEK B, WU Y, XU J. Computational lower bounds for community detection on random graphs［C］∥Proceedings of The 28th Conference on Learning Theory. Paris, France: JMLR, Inc, 2015: 899928.

[1]	王聚团, 戚晓宁, 黄志明. 水下生产管汇测试技术及其改进研究[J]. 海洋工程装备与技术, 2022, 9(2): 43-49.
[2]	袁振钦, 邹科, 孙亚峰, 刘刚, 屈衍, 李居跃. 基于时域分析法的动态电缆疲劳分析[J]. 海洋工程装备与技术, 2022, 9(2): 50-55.
[3]	王娟, 杨明旺, 郑茂尧, 刘凌云, 赵立君. 高强钢在大型半潜式平台组块建造中的应用[J]. 海洋工程装备与技术, 2022, 9(1): 27-31.
[4]	陈欣, 赵晓磊, 王立坤, 肖德明, 张腾月. 深水大型吸力锚建造技术研究[J]. 海洋工程装备与技术, 2022, 9(1): 32-36.
[5]	尹彦坤, 易涤非. 半潜式生产平台船体结构关键节点工程临界评估[J]. 海洋工程装备与技术, 2022, 9(1): 52-57.
[6]	ZHANG Shengfa (张胜发), TANG Na (唐纳), SHEN Guofeng (沈国峰), WANG Han (王悍), QIAO Shan (乔杉). Universal Software Architecture of Magnetic Resonance-Guided Focused Ultrasound Surgery System and Experimental Study[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 471-481.
[7]	MA Qunsheng (马群圣), CEN Xingxing (岑星星), YUAN Junyi (袁骏毅), HOU Xumin (侯旭敏). Word Embedding Bootstrapped Deep Active Learning Method to Information Extraction on Chinese Electronic Medical Record[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 494-502.
[8]	安庆升, 孙立东, 武秋生. 碳纤维增强复合材料发射筒设计研究[J]. 空天防御, 2021, 4(2): 13-.
[9]	KONG Xiangqiang (孔祥强), MENG Xiangxi (孟祥熙), LI Jianbo (李见波), SHANG Yanping (尚燕平), CUI Fulin (崔福林) . Comparative Study on Two-Stage Absorption Refrigeration Systems with Different Working Pairs[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 155-162.
[10]	ZHUANG Weimin (庄蔚敏), WANG Pengyue (王鹏跃), AO Wenhong (熬文宏), CHEN Gang (陈刚) . Experiment and Simulation of Impact Response of Woven CFRP Laminates with Different Stacking Angles[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 218-230.
[11]	ZHOU Xuhui (周旭辉), ZHANG Wenguang (张文光), XIE Jie (谢颉). Effects of Micro-Milling and Laser Engraving on Processing Quality and Implantation Mechanics of PEG-Dexamethasone Coated Neural Probe[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 1-9.
[12]	HUANG Ningning (黄宁宁), MA Yixin (马艺馨), ZHANG Mingzhu (张明珠), GE Hao (葛浩), WU Huawei (吴华伟). Finite Element Modeling of Human Thorax Based on MRI Images for EIT Image Reconstruction[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 33-39.
[13]	WANG Xianjin, GAO Xu, YU Kuigang . Fixture Locating Modelling and Optimization Research of Aluminum Alloy Sidewall in a High-Speed Train Body[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 706-713.
[14]	QIAO Xing, MA Dan, YAO Xuliang, FENG Baolin. Stability and Numerical Analysis of a Standby System[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 769-778.
[15]	WU Jin, MIN Yu, YANG Xiaodie, MA Simin . Micro-Expression Recognition Algorithm Based on Information Entropy Feature[J]. Journal of Shanghai Jiao Tong University(Science), 2020, 25(5): 589-599.