{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:59:15Z","timestamp":1725469155423},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_27","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"313-324","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues"],"prefix":"10.1007","author":[{"given":"Suguru","family":"Tamaki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"27_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1137\/080729256","volume":"40","author":"C. Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM Journal on Computing\u00a040(2), 567\u2013596 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 563\u2013572 (2010)","DOI":"10.1109\/FOCS.2010.59"},{"issue":"1","key":"27_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s101070100271","volume":"92","author":"S. Arora","year":"2002","unstructured":"Arora, S., Frieze, A.M., Kaplan, H.: A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Mathematical Programming\u00a092(1), 1\u201336 (2002)","journal-title":"Mathematical Programming"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Khot, S., Kolla, A., Steurer, D., Tulsiani, M., Vishnoi, N.K.: Unique games on expanding constraint graphs are easy: extended abstract. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 21\u201328 (2008)","DOI":"10.1145\/1374376.1374380"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B., Raghavendra, P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 472\u2013481 (2011); Full version: Electronic Colloquium on Computational Complexity (ECCC) TR11-65","DOI":"10.1109\/FOCS.2011.95"},{"issue":"4","key":"27_CR6","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s00453-008-9191-1","volume":"56","author":"M. Charikar","year":"2010","unstructured":"Charikar, M., Hajiaghayi, M.T., Karloff, H.J., Rao, S.: \n                    \n                      \n                    \n                    $\\ell_2^2$\n                   spreading metrics for vertex ordering problems. Algorithmica\u00a056(4), 577\u2013604 (2010)","journal-title":"Algorithmica"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Khot, S., Saket, R., Vishnoi, N.K.: Integrality gaps for sparsest cut and minimum linear arrangement problems. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 537\u2013546 (2006)","DOI":"10.1145\/1132516.1132594"},{"issue":"1","key":"27_CR8","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.ipl.2006.07.009","volume":"101","author":"U. Feige","year":"2007","unstructured":"Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Information Processing Letters\u00a0101(1), 26\u201329 (2007)","journal-title":"Information Processing Letters"},{"key":"27_CR9","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"27_CR10","unstructured":"Guruswami, V., Sinop, A.K.: Certifying graph expansion and non-uniform sparsity via generalized spectra. CoRR abs\/1112.4109 (2011)"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with PSD objectives. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 482\u2013491 (2011); Full version: Electronic Colloquium on Computational Complexity (ECCC) TR11-66","DOI":"10.1109\/FOCS.2011.36"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"key":"27_CR13","unstructured":"Kolla, A., Tulsiani, M.: Playing random and expanding unique games (unpublished manuscript)"},{"issue":"3","key":"27_CR14","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1137\/S1052623400380079","volume":"12","author":"J. Lasserre","year":"2002","unstructured":"Lasserre, J.: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM Journal on Optimization\u00a012(3), 756\u2013769 (2002)","journal-title":"SIAM Journal on Optimization"},{"key":"27_CR15","unstructured":"Lee, J.R., Gharan, S.O., Trevisan, L.: Multi-way spectral partitioning and higher-order cheeger inequalities. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 1117\u20131130 (2012); Full version: arXiv:1111.1055"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 755\u2013764 (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC) (to appear, 2012); Full version: Electronic Colloquium on Computational Complexity (ECCC) TR10-172","DOI":"10.1109\/CCC.2012.43"},{"issue":"2","key":"27_CR18","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1137\/S0097539702413197","volume":"34","author":"S. Rao","year":"2004","unstructured":"Rao, S., Richa, A.W.: New approximation techniques for some linear ordering problems. SIAM Journal on Computing\u00a034(2), 388\u2013404 (2004)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:06:50Z","timestamp":1558314410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}