{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T08:40:26Z","timestamp":1775205626114,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T00:00:00Z","timestamp":1534809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["26330011, 18K11164 and JP17H04676"],"award-info":[{"award-number":["26330011, 18K11164 and JP17H04676"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            Given an\n            <jats:italic>n<\/jats:italic>\n            -vertex undirected graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) and positive edge weights {\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>e<\/jats:sub>\n            }\n            <jats:italic>\n              <jats:sub>e\u2208E<\/jats:sub>\n            <\/jats:italic>\n            , a linear arrangement is a permutation \u03c0 : V \u2192 {1, 2, \u2026,\n            <jats:italic>n<\/jats:italic>\n            }. The value of the arrangement is\n            <jats:bold>val<\/jats:bold>\n            (\n            <jats:italic>G<\/jats:italic>\n            , \u03c0) := 1\/n\u2211\n            <jats:sub>\n              e ={\n              <jats:italic>u, v<\/jats:italic>\n              } \u2208\n              <jats:italic>E<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>\n              w\n              <jats:sub>e<\/jats:sub>\n            <\/jats:italic>\n            |\u03c0(\n            <jats:italic>u<\/jats:italic>\n            ) \u2212 \u03c0 (\n            <jats:italic>v<\/jats:italic>\n            )|. In the minimum linear arrangement problem, the goal is to find a linear arrangement \u03c0\n            <jats:sup>*<\/jats:sup>\n            that achieves\n            <jats:bold>val<\/jats:bold>\n            (\n            <jats:italic>G<\/jats:italic>\n            , \u03c0\n            <jats:sup>*<\/jats:sup>\n            ) = MLA(\n            <jats:italic>G<\/jats:italic>\n            ) := min\n            <jats:sub>\u03c0<\/jats:sub>\n            <jats:bold>val<\/jats:bold>\n            (\n            <jats:italic>G<\/jats:italic>\n            , \u03c0).\n          <\/jats:p>\n          <jats:p>\n            In this article, we show that for any \u03f5 &gt; 0 and positive integer\n            <jats:italic>r<\/jats:italic>\n            , there is an\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>r<\/jats:italic>\n              \/\u03f5)\n            <\/jats:sup>\n            -time randomized algorithm that, given a graph\n            <jats:italic>G<\/jats:italic>\n            , returns a linear arrangement \u03c0, such that\n          <\/jats:p>\n          <jats:p>\n            <jats:bold>val<\/jats:bold>\n            (\n            <jats:italic>G<\/jats:italic>\n            , \u03c0) \u2264 (1 + 2\/(1 \u2212 \u03b5)\u03bb\n            <jats:sub>r<\/jats:sub>\n            (\n            <jats:italic>L<\/jats:italic>\n            )) MLA(\n            <jats:italic>G<\/jats:italic>\n            ) +\n            <jats:italic>O<\/jats:italic>\n            (\u221alog\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>n<\/jats:italic>\n            \u2211\n            <jats:sub>\n              <jats:italic>e \u2208 E<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>\n              w\n              <jats:sub>e<\/jats:sub>\n            <\/jats:italic>\n            )\n          <\/jats:p>\n          <jats:p>\n            with high probability, where\n            <jats:italic>L<\/jats:italic>\n            is the normalized Laplacian of\n            <jats:italic>G<\/jats:italic>\n            and \u03bb\n            <jats:sub>r<\/jats:sub>\n            (\n            <jats:italic>L<\/jats:italic>\n            ) is the\n            <jats:italic>r<\/jats:italic>\n            th smallest eigenvalue of\n            <jats:italic>L<\/jats:italic>\n            . Our algorithm gives a constant factor approximation for regular graphs that are weak expanders.\n          <\/jats:p>","DOI":"10.1145\/3228342","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T12:09:47Z","timestamp":1534853387000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues"],"prefix":"10.1145","volume":"14","author":[{"given":"Suguru","family":"Tamaki","sequence":"first","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729256"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100271"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1714388.1714398"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132594"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2207816"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.07.009"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095211"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627839"},{"key":"e_1_2_1_14_1","volume-title":"Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and quadratic IPs. CoRR abs\/1312.3024","author":"Guruswami Venkatesan","year":"2013","unstructured":"Venkatesan Guruswami and Ali Kemal Sinop. 2013b. Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and quadratic IPs. CoRR abs\/1312.3024 (2013)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_16_1","unstructured":"Alexandra Kolla and Madhur Tulsiani. 2007. Playing random and expanding unique games. Unpublished manuscript."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400380079"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2665063"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702413197"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3228342","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3228342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:34Z","timestamp":1750212454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3228342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,21]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3228342"],"URL":"https:\/\/doi.org\/10.1145\/3228342","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,21]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}