{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:20Z","timestamp":1740122420903,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10878-020-00552-w","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T03:02:27Z","timestamp":1583722947000},"page":"1880-1899","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An approximation algorithm for the maximum spectral subgraph problem"],"prefix":"10.1007","volume":"44","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4707-8388","authenticated-orcid":false,"given":"Paul","family":"Beaujean","sequence":"additional","affiliation":[]},{"given":"\u00c9ric","family":"Gourdin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"issue":"2","key":"552_CR1","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10208-016-9341-9","volume":"18","author":"AS Bandeira","year":"2018","unstructured":"Bandeira AS (2018) Random Laplacian matrices and convex relaxations. Found Comput Math 18(2):345\u2013379","journal-title":"Found Comput Math"},{"issue":"1","key":"552_CR2","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1006\/jagm.1998.0998","volume":"31","author":"C Bazgan","year":"1999","unstructured":"Bazgan C, Santha M, Tuza Z (1999) On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs. J Algorithms 31(1):249\u2013268","journal-title":"J Algorithms"},{"key":"552_CR3","volume-title":"Matrix analysis","author":"R Bhatia","year":"2013","unstructured":"Bhatia R (2013) Matrix analysis, vol 169. Springer, Berlin"},{"issue":"2","key":"552_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0012-365X(80)90054-0","volume":"32","author":"B Bollob\u00e1s","year":"1980","unstructured":"Bollob\u00e1s B (1980) The distribution of the maximum degree of a random graph. Discrete Math 32(2):201\u2013203","journal-title":"Discrete Math"},{"issue":"4","key":"552_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1284680.1284681","volume":"10","author":"D Chakrabarti","year":"2008","unstructured":"Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM Trans Inf Syst Secur (TISSEC) 10(4):1","journal-title":"ACM Trans Inf Syst Secur (TISSEC)"},{"issue":"1","key":"552_CR6","doi-asserted-by":"publisher","first-page":"215","DOI":"10.37236\/702","volume":"18","author":"F Chung","year":"2011","unstructured":"Chung F, Radcliffe M (2011) On the spectra of general random graphs. Electron J Comb 18(1):215","journal-title":"Electron J Comb"},{"issue":"3","key":"552_CR7","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/15M103114X","volume":"26","author":"E de Klerk","year":"2016","unstructured":"de Klerk E, Vallentin F (2016) On the Turing model complexity of interior point methods for semidefinite programming. SIAM J Optim 26(3):1944\u20131961","journal-title":"SIAM J Optim"},{"doi-asserted-by":"crossref","unstructured":"Ganesh A, Massouli\u00e9 L, Towsley D (2005) The effect of network topology on the spread of epidemics. In: Proceedings of the annual joint conference of the IEEE computer and communications societies (INFOCOM 2005), vol 2, pp 1455\u20131466","key":"552_CR8","DOI":"10.1109\/INFCOM.2005.1498374"},{"doi-asserted-by":"crossref","unstructured":"Ghosh A, Boyd S (2006) Growing well-connected graphs. In: Proceedings of the IEEE conference on decision and control (CDC 2006), IEEE, pp 6605\u20136611","key":"552_CR9","DOI":"10.1109\/CDC.2006.377282"},{"issue":"4","key":"552_CR10","first-page":"1141","volume":"30","author":"EN Gilbert","year":"1959","unstructured":"Gilbert EN (1959) Random graphs. Ann Math. Stat 30(4):1141\u20131144","journal-title":"Stat"},{"issue":"6","key":"552_CR11","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM (JACM) 42(6):1115\u20131145","journal-title":"J ACM (JACM)"},{"doi-asserted-by":"crossref","unstructured":"Kolla A, Makarychev Y, Saberi A, Teng S-H (2010) Subgraph sparsification and nearly optimal ultrasparsifiers. In: Proceedings of the ACM symposium on theory of computing (STOC 2010), ACM, pp 57\u201366","key":"552_CR12","DOI":"10.1145\/1806689.1806699"},{"issue":"01","key":"552_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1017\/S0963548302005424","volume":"12","author":"M Krivelevich","year":"2003","unstructured":"Krivelevich M, Sudakov B (2003) The largest eigenvalue of sparse random graphs. Comb Probab Comput 12(01):61\u201372","journal-title":"Comb Probab Comput"},{"issue":"3","key":"552_CR14","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796\u2013817","journal-title":"SIAM J Optim"},{"key":"552_CR15","first-page":"393","volume":"12","author":"M Laurent","year":"2005","unstructured":"Laurent M, Rendl F (2005) Semidefinite programming and integer programming. Handb Oper Res Manag Sci 12:393\u2013514","journal-title":"Handb Oper Res Manag Sci"},{"issue":"3","key":"552_CR16","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1002\/rsa.20713","volume":"51","author":"CM Le","year":"2017","unstructured":"Le CM, Elizaveta L, Roman V (2017) Concentration and regularization of random graphs. Random Struct Algorithms 51(3):538\u2013561","journal-title":"Random Struct Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Mehdi SA, Khalid J, Khayam SA (2011) Revisiting traffic anomaly detection using software defined networking. In: Proceedings of the international workshop on recent advances in intrusion detection (RAID 2011), Springer, pp 161\u2013180","key":"552_CR17","DOI":"10.1007\/978-3-642-23644-0_9"},{"issue":"6","key":"552_CR18","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.orl.2008.09.001","volume":"36","author":"D Mosk-Aoyama","year":"2008","unstructured":"Mosk-Aoyama D (2008) Maximum algebraic connectivity augmentation is NP-hard. Oper Res Lett 36(6):677\u2013679","journal-title":"Oper Res Lett"},{"key":"552_CR19","volume-title":"Randomized algorithms","author":"R Motwani","year":"2010","unstructured":"Motwani R, Raghavan P (2010) Randomized algorithms. Chapman & Hall\/CRC, Boca Raton"},{"issue":"3","key":"552_CR20","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1287\/moor.1110.0498","volume":"36","author":"J Nie","year":"2011","unstructured":"Nie J (2011) Polynomial matrix inequality and semidefinite representation. Math Oper Res 36(3):398\u2013415","journal-title":"Math Oper Res"},{"doi-asserted-by":"crossref","unstructured":"Pan VY, Chen ZQ (1999) The complexity of the matrix eigenproblem. In: Proceedings of the ACM symposium on theory of computing (STOC 1999), pp 507\u2013516","key":"552_CR21","DOI":"10.1145\/301250.301389"},{"issue":"2","key":"552_CR22","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo PA (2003) Semidefinite programming relaxations for semialgebraic problems. Math Program 96(2):293\u2013320","journal-title":"Math Program"},{"doi-asserted-by":"crossref","unstructured":"Prakash BA, Chakrabarti D, Faloutsos M, Valler N, Faloutsos C (2011) Threshold conditions for arbitrary cascade models on arbitrary networks. In: Proceedings of the IEEE international conference on data mining (ICDM 2011), pp 537\u2013546","key":"552_CR23","DOI":"10.1109\/ICDM.2011.145"},{"issue":"4","key":"552_CR24","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan P, Tompson CD (1987) Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4):365\u2013374","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Raghavendra P (2008) Optimal algorithms and inapproximability results for every CSP? In: Proceedings of the ACM symposium on theory of computing (STOC 2008), ACM, pp 245\u2013254","key":"552_CR25","DOI":"10.1145\/1374376.1374414"},{"doi-asserted-by":"crossref","unstructured":"Saha S, Adiga A, Prakash BA, Vullikanti AKS (2015) Approximation algorithms for reducing the spectral radius to control epidemic spread. In: Proceedings of the SIAM international conference on data mining (SDM 2015), pp 568\u2013576","key":"552_CR26","DOI":"10.1137\/1.9781611974010.64"},{"unstructured":"Shin S, Gu G (2012) Cloudwatcher: network security monitoring using openflow in dynamic cloud networks (or: how to provide security monitoring as a service in clouds?). In: Proceedings of the IEEE international conference on network protocols (ICNP 2012), IEEE, pp 1\u20136","key":"552_CR27"},{"issue":"433","key":"552_CR28","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1016\/j.laa.2010.06.015","volume":"8","author":"D Stevanovi\u0107","year":"2010","unstructured":"Stevanovi\u0107 D (2010) Resolution of AutoGraphiX conjectures relating the index and matching number of graphs. Linear Algebra Appl 8(433):1674\u20131677","journal-title":"Linear Algebra Appl"},{"issue":"1\u20132","key":"552_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000048","volume":"8","author":"JA Tropp","year":"2015","unstructured":"Tropp JA et al (2015) An introduction to matrix concentration inequalities. Found Trends Mach Learn 8(1\u20132):1\u2013230","journal-title":"Found Trends Mach Learn"},{"key":"552_CR30","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-1-4939-7005-6_4","volume-title":"Convexity and concentration","author":"R van Handel","year":"2017","unstructured":"van Handel R (2017) Structured random matrices. In: Carlen E, Madiman M, Werner E (eds) Convexity and concentration. Springer, New York, pp 107\u2013156"},{"key":"552_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921681","volume-title":"Graph spectra for complex networks","author":"P Van Mieghem","year":"2010","unstructured":"Van Mieghem P (2010) Graph spectra for complex networks. Cambridge University Press, Cambridge"},{"issue":"1","key":"552_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TNET.2008.925623","volume":"17","author":"P Van Mieghem","year":"2009","unstructured":"Van Mieghem P, Omic J, Kooij R (2009) Virus spread in networks. IEEE\/ACM Trans Netw (TON) 17(1):1\u201314","journal-title":"IEEE\/ACM Trans Netw (TON)"},{"issue":"1","key":"552_CR33","doi-asserted-by":"publisher","first-page":"016101","DOI":"10.1103\/PhysRevE.84.016101","volume":"84","author":"P Van Mieghem","year":"2011","unstructured":"Van Mieghem P, Stevanovi\u0107 D, Kuipers F, Li C, Van De Bovenkamp R, Liu D, Wang H (2011) Decreasing the spectral radius of a graph by link removals. Phys Rev E 84(1):016101","journal-title":"Phys Rev E"},{"issue":"1","key":"552_CR34","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM Rev 38(1):49\u201395","journal-title":"SIAM Rev"},{"doi-asserted-by":"crossref","unstructured":"Wang Y, Chakrabarti D, Wang C, Faloutsos C (2003) Epidemic spreading in real networks: an eigenvalue viewpoint. In: Proceedings of the international symposium on reliable distributed systems (SRDS 2003), IEEE, pp 25\u201334","key":"552_CR35","DOI":"10.1109\/RELDIS.2003.1238052"},{"doi-asserted-by":"crossref","unstructured":"Wang G, Ng TS, Shaikh A (2012) Programming your network at run-time for big data applications. In: Proceedings of the workshop on hot topics in software defined networks (HotSDN 2012), ACM, pp 103\u2013108","key":"552_CR36","DOI":"10.1145\/2342441.2342462"},{"key":"552_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, Cambridge"},{"doi-asserted-by":"crossref","unstructured":"Zhang Y, Adiga A, Vullikanti A, Prakash BA (2015) Controlling propagation at group scale on networks. In: Proceedings of the international conference on data mining (ICDM 2015), pp 619\u2013628","key":"552_CR38","DOI":"10.1109\/ICDM.2015.59"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00552-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00552-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00552-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:47:14Z","timestamp":1664354834000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00552-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["552"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00552-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"9 March 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}