{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T03:11:35Z","timestamp":1775272295229,"version":"3.50.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030046507","type":"print"},{"value":"9783030046514","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_8","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T14:56:50Z","timestamp":1542293810000},"page":"108-122","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[]},{"given":"Paul","family":"Beaujean","sequence":"additional","affiliation":[]},{"given":"\u00c9ric","family":"Gourdin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8","volume-title":"Matrix Analysis","author":"R Bhatia","year":"2013","unstructured":"Bhatia, R.: Matrix Analysis, vol. 169. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-1-4612-0653-8"},{"issue":"4","key":"8_CR2","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.: Epidemic thresholds in real networks. ACM Trans. Inf. Syst. Secur. (TISSEC) 10(4), 1 (2008)","journal-title":"ACM Trans. Inf. Syst. Secur. (TISSEC)"},{"issue":"1","key":"8_CR3","doi-asserted-by":"crossref","first-page":"215","DOI":"10.37236\/702","volume":"18","author":"F Chung","year":"2011","unstructured":"Chung, F., Radcliffe, M.: On the spectra of general random graphs. Electron. J. Comb. 18(1), 215 (2011)","journal-title":"Electron. J. Comb."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Ganesh, A., Massouli\u00e9, L., Towsley, D.: 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 (2005)","DOI":"10.1109\/INFCOM.2005.1498374"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Ghosh, A., Boyd, S.: Growing well-connected graphs. In: Proceedings of the IEEE Conference on Decision and Control (CDC 2006), pp. 6605\u20136611. IEEE (2006)","DOI":"10.1109\/CDC.2006.377282"},{"issue":"6","key":"8_CR6","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM (JACM)"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Kolla, A., Makarychev, Y., Saberi, A., Teng, S-H.: Subgraph sparsification and nearly optimal ultrasparsifiers. In: Proceedings of the ACM Symposium on Theory of Computing (STOC 2010), pp. 57\u201366. ACM (2010)","DOI":"10.1145\/1806689.1806699"},{"issue":"3","key":"8_CR8","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"8_CR9","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1002\/rsa.20713","volume":"51","author":"CM Le","year":"2017","unstructured":"Le, C.M., Levina, E., Vershynin, R.: Concentration and regularization of random graphs. Random Struct. Algorithms 51(3), 538\u2013561 (2017)","journal-title":"Random Struct. Algorithms"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-642-23644-0_9","volume-title":"Recent Advances in Intrusion Detection","author":"SA Mehdi","year":"2011","unstructured":"Mehdi, S.A., Khalid, J., Khayam, S.A.: Revisiting traffic anomaly detection using software defined networking. In: Sommer, R., Balzarotti, D., Maier, G. (eds.) RAID 2011. LNCS, vol. 6961, pp. 161\u2013180. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23644-0_9"},{"issue":"6","key":"8_CR11","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.: Maximum algebraic connectivity augmentation is NP-hard. Oper. Res. Lett. 36(6), 677\u2013679 (2008)","journal-title":"Oper. Res. Lett."},{"key":"8_CR12","volume-title":"Randomized Algorithms","author":"R Motwani","year":"2010","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Chapman & Hall\/CRC, Boca Raton (2010)"},{"issue":"3","key":"8_CR13","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1287\/moor.1110.0498","volume":"36","author":"J Nie","year":"2011","unstructured":"Nie, J.: Polynomial matrix inequality and semidefinite representation. Math. Oper. Res. 36(3), 398\u2013415 (2011)","journal-title":"Math. Oper. Res."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Pan, V.Y., Chen, Z.Q.: The complexity of the matrix eigenproblem. In: Proceedings of the ACM Symposium on Theory of Computing (STOC 1999), pp. 507\u2013516 (1999)","DOI":"10.1145\/301250.301389"},{"issue":"2","key":"8_CR15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293\u2013320 (2003)","journal-title":"Math. Program."},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Aditya Prakash, B., Chakrabarti, D., Faloutsos, M., Valler, N., Faloutsos, C.: Threshold conditions for arbitrary cascade models on arbitrary networks. In: Proceedings of the IEEE International Conference on Data Mining (ICDM 2011), pp. 537\u2013546 (2011)","DOI":"10.1109\/ICDM.2011.145"},{"issue":"4","key":"8_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan, P., Tompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proceedings of the ACM Symposium on Theory of Computing (STOC 2008), pp. 245\u2013254. ACM (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1137\/1.9781611974010.64","volume-title":"Proceedings of the 2015 SIAM International Conference on Data Mining","author":"Sudip Saha","year":"2015","unstructured":"Saha, S., Adiga, A., Aditya Prakash, B., Vullikanti, A.K.S.: 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 (2015)"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Shin, S., Gu, G.: 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), pp. 1\u20136. IEEE (2012)","DOI":"10.1109\/ICNP.2012.6459946"},{"issue":"433","key":"8_CR21","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.: Resolution of AutoGraphiX conjectures relating the index and matching number of graphs. Linear Algebra Appl. 8(433), 1674\u20131677 (2010)","journal-title":"Linear Algebra Appl."},{"issue":"1\u20132","key":"8_CR22","first-page":"1","volume":"8","author":"JA Tropp","year":"2015","unstructured":"Tropp, J.A., et al.: An introduction to matrix concentration inequalities. Found. Trends\u00ae Mach. Learn. 8(1\u20132), 1\u2013230 (2015)","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"8_CR23","series-title":"The IMA Volumes in Mathematics and its Applications","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.: Structured random matrices. In: Carlen, E., Madiman, M., Werner, E.M. (eds.) Convexity and Concentration. TIVMA, vol. 161, pp. 107\u2013156. Springer, New York (2017). https:\/\/doi.org\/10.1007\/978-1-4939-7005-6_4"},{"key":"8_CR24","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.: Graph Spectra for Complex Networks. Cambridge University Press, Cambridge (2010)"},{"issue":"1","key":"8_CR25","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.: Virus spread in networks. IEEE\/ACM Trans. Netw. (TON) 17(1), 1\u201314 (2009)","journal-title":"IEEE\/ACM Trans. Netw. (TON)"},{"issue":"1","key":"8_CR26","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., et al.: Decreasing the spectral radius of a graph by link removals. Phys. Rev. E 84(1), 016101 (2011)","journal-title":"Phys. Rev. E"},{"key":"8_CR27","doi-asserted-by":"crossref","unstructured":"Wang, G., Ng, T.S., Shaikh, A.: Programming your network at run-time for big data applications. In: Proceedings of the Workshop on Hot Topics in Software Defined Networks (HotSDN 2012), pp. 103\u2013108. ACM (2012)","DOI":"10.1145\/2342441.2342462"},{"key":"8_CR28","unstructured":"Wang, Y., Chakrabarti, D., Wang, C., Faloutsos, C.: Epidemic spreading in real networks: an eigenvalue viewpoint. In: Proceedings of the International Symposium on Reliable Distributed Systems (SRDS 2003), pp. 25\u201334. IEEE (2003)"},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Adiga, A., Vullikanti, A., Aditya Prakash, B.: Controlling propagation at group scale on networks. In: Proceedings of the International Conference on Data Mining (ICDM 2015), pp. 619\u2013628 (2015)","DOI":"10.1109\/ICDM.2015.59"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T02:31:52Z","timestamp":1775269912000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}