Hidden Hamiltonian Cycle Recovery via Linear Programming

References

• Abbe E, Sandon C (2015) Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. Proc. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 670–688.Google Scholar
• Abbe E, Bandeira AS, Hall G (2016) Exact recovery in the stochastic block model. IEEE Trans. Inform. Theory 62(1):471–487.Google Scholar
• Agarwal N, Bandeira AS, Koiliaris K, Kolla A (2017) Multisection in the stochastic block model using semidefinite programming. Boche H, Caire G, Calderbank R, März M, Kutyniok G, Mathar R, eds. Compressed Sensing and Its Applications, Applied and Numerical Harmonic Analysis (Birkhäuser, Cham, Switzerland), 125–162.Google Scholar
• Allen-Zhu Z, Orecchia L (2019) Nearly linear-time packing and covering LP solvers. Math. Programming 175(1–2):307–353.Crossref, Google Scholar
• Alon N, Krivelevich M, Sudakov B (1998) Finding a large hidden clique in a random graph. Random Structures Algorithms 13(3–4):457–466.Crossref, Google Scholar
• Atkins JE, Boman EG, Hendrickson B (1998) A spectral algorithm for seriation and the consecutive ones problem. SIAM J. Comput. 28(1):297–310.Crossref, Google Scholar
• Balinski ML (1965) Integer programming: Methods, uses, computations. Management Sci. 12(3):253–313.Link, Google Scholar
• Bandeira A (2018) Random Laplacian matrices and convex relaxations. Foundations Comput. Math. 18(2):345–379.Google Scholar
• Barak B, Hopkins SB, Kelner JA, Kothari P, Moitra A, Potechin A (2016) A nearly tight sum-of-squares lower bound for the planted clique problem. Proc. IEEE 57th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 428–437.Google Scholar
• Bayati M, Borgs C, Chayes J, Zecchina R (2011) Belief propagation for weighted b-matchings on arbitrary graphs and its relation to linear programs with integer solutions. SIAM J. Discrete Math. 25(2):989–1011.Crossref, Google Scholar
• Bordenave C, Lelarge M, Massoulié L (2015) Non-backtracking spectrum of random graphs: Community detection and non-regular Ramanujan graphs. Proc. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 1347–1357.Google Scholar
• Boyd S, Carr R (1999) A new bound for the ratio between the 2-matching problem and its linear programming relaxation. Math. Programming 86(3):499–514.Crossref, Google Scholar
• Broder AZ, Frieze AM, Shamir E (1994) Finding hidden Hamiltonian cycles. Random Structures Algorithms 5(3):395–410.Crossref, Google Scholar
• Cai T, Liang T, Rakhlin A (2017) On detection and structural reconstruction of small-world random networks. IEEE Trans. Network Sci. Engrg. 4(3):165–176.Crossref, Google Scholar
• Chen K, Chen K, Muller HG, Wang JL (2011) Stringing high-dimensional data for functional analysis. J. Amer. Statist. Assoc. 106(493):275–284.Crossref, Google Scholar
• Chlamtác E, Tulsiani M (2012) Convex relaxations and integrality gaps. Anjos M, Lasserre J, eds. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, Boston), 139–169.Crossref, Google Scholar
• Condon A, Karp RM (2001) Algorithms for graph partitioning on the planted partition model. Random Structures Algorithms 18(2):116–140.Crossref, Google Scholar
• Cvetković D, Čangalović M, Kovačević-Vujčić V (1999) Semidefinite programming methods for the symmetric traveling salesman problem. Cornuéjols G, Burkard RE, Woeginger GJ, eds. Proc. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 126–136.Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• De Klerk E, Pasechnik DV, Sotirov R (2008) On semidefinite programming relaxations of the traveling salesman problem. SIAM J. Optim. 19(4):1559–1573.Crossref, Google Scholar
• Deshpande Y, Montanari A (2015) Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. Grünwald P, Hazan E, Kale S, eds. Proc. 28th Conf. Learn. Theory, vol. 40 (PMLR, Paris), 523–562.Google Scholar
• Edmonds J (1965a) Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl. Bureau Standards B 69B(55–56):125–130.Crossref, Google Scholar
• Edmonds J (1965b) Paths, trees, and flowers. Canadian J. Math. 17(3):449–467.Crossref, Google Scholar
• Fogel F, Jenatton R, Bach F, d’Aspremont A (2013) Convex relaxations for permutation problems. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 26 (Curran Associates, Red Hook, NY), 1016–1024.Google Scholar
• Hajek B, Wu Y, Xu J (2016a) Achieving exact cluster recovery threshold via semidefinite programming. IEEE Trans. Inform. Theory 62(5):2788–2797.Google Scholar
• Hajek B, Wu Y, Xu J (2016b) Achieving exact cluster recovery threshold via semidefinite programming: Extensions. IEEE Trans. Inform. Theory 62(10):5918–5937.Crossref, Google Scholar
• Hajek B, Wu Y, Xu J (2016c) Semidefinite programs for exact recovery of a hidden community. Feldman V, Rakhlin A, Shamir O, eds. Proc. 29th Conf. Learn. Theory, vol. 49 (PMLR, New York), 1051–1095.Google Scholar
• Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6):1138–1162.Link, Google Scholar
• Jerrum M (1992) Large cliques elude the Metropolis process. Random Structures Algorithms 3(4):347–359.Google Scholar
• Jog V, Loh P-L (2015) Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence. Preprint arXiv 1509.06418, submitted September 21, https://arxiv.org/abs/1509.06418.Google Scholar
• Kendall DG (1971) Abundance matrices and seriation in archaeology. Probab. Theory Related Fields 17(2):104–112.Google Scholar
• Kotzig A (1968) Moves without forbidden transitions in a graph. Matematický časopis 18(1):76–80.Google Scholar
• Letchford AN, Reinelt G, Theis DO (2008) Odd minimum cut sets and b-matchings revisited. SIAM J. Discrete Math. 22(4):1480–1487.Crossref, Google Scholar
• Lieberman-Aiden E, Van Berkum NL, Williams L, Imakaev M, Ragoczy T, Telling A, Amit I, et al.. (2009) Comprehensive mapping of long-range interactions reveals folding principles of the human genome. Science 326(5950):289–293.Google Scholar
• Lim CH, Wright S (2014) Beyond the Birkhoff polytope: Convex relaxations for vector permutation problems. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 27 (Curran Associates, Red Hook, NY), 2168–2176.Google Scholar
• Lovász L (2012) Large Networks and Graph Limits, Colloquium Publications, vol. 60 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Mallows CL (1957) Non-null ranking models. I. Biometrika 44(1/2):114–130.Crossref, Google Scholar
• Massoulié L (2013) Community detection thresholds and the weak Ramanujan property. Proc. 46th Annual ACM Sympos. Theory Comput. (ACM, New York), 694–703.Google Scholar
• McSherry F (2001) Spectral partitioning of random graphs. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 529–537.Google Scholar
• Meka R, Potechin A, Wigderson A (2015) Sum-of-squares lower bounds for planted clique. Proc. 47th Annual ACM Sympos. Theory Comput. (ACM, New York), 87–96.Google Scholar
• Mossel E, Neeman J, Sly A (2015) Consistency thresholds for the planted bisection model. Proc. 47th Annual ACM Sympos. Theory Comput. (ACM, New York), 69–75.Google Scholar
• Motahari AS, Bresler G, Tse D (2013) Information theory of DNA shotgun sequencing. IEEE Trans. Inform. Theory 59(10):6273–6289.Crossref, Google Scholar
• Perry W, Wein A (2017) A semidefinite program for unbalanced multisection in the stochastic block model. Proc. 2017 International Conference on Sampling Theory and Applications (SampTA) (IEEE, Piscataway, NJ), 64–67.Google Scholar
• Pevzner PA (1995) DNA physical mapping and alternating Eulerian cycles in colored graphs. Algorithmica 13(1–2):77–105.Crossref, Google Scholar
• Putnam NH, O’Connell BL, Stites JC, Rice BJ, Blanchette M, Calef R, Troll CJ, Fields A, Hartley PD, Sugnet CW (2016) Chromosome-scale shotgun assembly using an in vitro method for long-range linkage. Genome Res. 26(3):342–350.Crossref, Google Scholar
• Rényi A (1961) On measures of entropy and information. Proc. 4th Berkeley Sympos. Math. Statist. Probab., vol. 1: Contributions Theory Statist. (University of California Press, Berkeley), 547–561.Google Scholar
• Robinson WS (1951) A method for chronologically ordering archaeological deposits. Amer. Antiquity 16(4):293–301.Crossref, Google Scholar
• Schalekamp F, Williamson DP, van Zuylen A (2013) 2-matchings, the traveling salesman problem, and the subtour LP: A proof of the Boyd-Carr conjecture. Math. Oper. Res. 39(2):403–417.Link, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24 (Springer Science & Business Media, New York).Google Scholar
• Watts DJ, Strogatz SH (1998) Collective dynamics of “small-world” networks. Nature 393(6684):440–442.Google Scholar
• Zhang AY, Zhou HH (2016) Minimax rates of community detection in stochastic block models. Ann. Statist. 44(5):2252–2280.Crossref, Google Scholar
• Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2(1):71–109.Crossref, Google Scholar