{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T00:20:56Z","timestamp":1768263656892,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642141645","type":"print"},{"value":"9783642141652","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_50","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:02Z","timestamp":1278321962000},"page":"594-604","source":"Crossref","is-referenced-by-count":9,"title":["Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm"],"prefix":"10.1007","author":[{"given":"Konstantin","family":"Makarychev","sequence":"first","affiliation":[]},{"given":"Rajsekar","family":"Manokaran","sequence":"additional","affiliation":[]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"50_CR1","doi-asserted-by":"crossref","unstructured":"Adams, W.P., Johnson, T.A.: Improved Linear Programming-based Lower Bounds for the Quadratic Assignment Problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a016, pp. 43\u201377 (1994)","DOI":"10.1090\/dimacs\/016\/02"},{"key":"50_CR2","doi-asserted-by":"crossref","unstructured":"Anstreicher, K.: Recent advances in the solution of quadratic assignment problems. In: Anstreicher, K. (ed.) ISMP, 2003. Copenhagen. Math. Program, Ser. B, vol.\u00a097(1-2), pp. 27\u201342 (2003)","DOI":"10.1007\/s10107-003-0437-z"},{"key":"50_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0190(00)00151-4","volume":"77","author":"E. Arkin","year":"2001","unstructured":"Arkin, E., Hassin, R., Sviridenko, M.: Approximating the Maximum Quadratic Assignment Problem. Information Processing Letters\u00a077, 13\u201316 (2001)","journal-title":"Information Processing Letters"},{"issue":"1","key":"50_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s101070100271","volume":"92","author":"S. Arora","year":"2002","unstructured":"Arora, S., Frieze, A., 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":"50_CR5","unstructured":"Arora, S., Lund, C.: Hardness of Approximations. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems. PWS Publishing (1996)"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM\u00a045(3)","DOI":"10.1145\/278298.278306"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM\u00a045(1), 70\u2013122","DOI":"10.1145\/273865.273901"},{"key":"50_CR8","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting High Log-Densities \u2013 an \n                    \n                      \n                    \n                    $O(n^{\\frac{1}{4}})$\n                   Approximation for Densest k-Subgraph. In: Proceedings of STOC (to appear, 2010)"},{"key":"50_CR9","first-page":"241","volume-title":"Handbook of Combinatorial Optimization","author":"R.E. Burkard","year":"1998","unstructured":"Burkard, R.E., Cela, E., Pardalos, P., Pitsoulis, L.S.: The quadratic assignment problem. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol.\u00a03, pp. 241\u2013339. Kluwer Academic Publishers, Dordrecht (1998)"},{"key":"50_CR10","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment Problems","author":"R.E. Burkard","year":"2009","unstructured":"Burkard, R.E., Dell\u2019Amico, M., Martello, S.: Assignment Problems. SIAM, Philadelphia (2009)"},{"key":"50_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2787-6","volume-title":"The Quadratic Assignment Problem: Theory and Algorithms","author":"E. Cela","year":"1998","unstructured":"Cela, E.: The Quadratic Assignment Problem: Theory and Algorithms. Springer, Heidelberg (1998)"},{"key":"50_CR12","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1287\/moor.1090.0419","volume":"34","author":"Y. Dong","year":"2009","unstructured":"Dong, Y., Wolkowicz, H.: A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem. Mathematics of Operations Research\u00a034, 1008\u20131022 (2009)","journal-title":"Mathematics of Operations Research"},{"key":"50_CR13","first-page":"59","volume":"6","author":"J. Dickey","year":"1972","unstructured":"Dickey, J., Hopkins, J.: Campus building arrangement using TOPAZ. Transportation Science\u00a06, 59\u201368 (1972)","journal-title":"Transportation Science"},{"key":"50_CR14","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1057\/jors.1991.21","volume":"42","author":"H. Eiselt","year":"1991","unstructured":"Eiselt, H., Laporte, G.: A combinatorial optimization problem arising in dartboard design. Journal of Operational Research Society\u00a042, 113\u2013118 (1991)","journal-title":"Journal of Operational Research Society"},{"key":"50_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1057\/jors.1977.29","volume":"28","author":"A. Elshafei","year":"1977","unstructured":"Elshafei, A.: Hospital layout as a quadratic assignment problem. Operations Research Quarterly\u00a028, 167\u2013179 (1977)","journal-title":"Operations Research Quarterly"},{"key":"50_CR16","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of STOC 2002 , pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"issue":"2","key":"50_CR17","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A. Frieze","year":"1999","unstructured":"Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica\u00a019(2), 175\u2013220 (1999)","journal-title":"Combinatorica"},{"key":"50_CR18","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1287\/opre.24.4.595","volume":"24","author":"A. Geoffrion","year":"1976","unstructured":"Geoffrion, A., Graves, G.: Scheduling parallel production lines with changeover costs: Practical applications of a quadratic assignment\/LP approach. Operations Research\u00a024, 596\u2013610 (1976)","journal-title":"Operations Research"},{"key":"50_CR19","doi-asserted-by":"crossref","unstructured":"Hassin, R., Levin, A., Sviridenko, M.: Approximating the minimum quadratic assignment problems. ACM Transactions on Algorithms\u00a06(1) (2009)","DOI":"10.1145\/1644015.1644033"},{"key":"50_CR20","doi-asserted-by":"crossref","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proceedings of FOCS 2004, pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"key":"50_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"T.C. Koopmans","year":"1957","unstructured":"Koopmans, T.C., Beckman, M.: Assignment problems and the location of economic activities. Econometrica\u00a025, 53\u201376 (1957)","journal-title":"Econometrica"},{"key":"50_CR22","doi-asserted-by":"crossref","unstructured":"Nagarajan, V., Sviridenko, M.: On the maximum quadratic assignment problem. Mathematics of Operations Research\u00a034(4), 859\u2013868 (2009); preliminary version appeared in Proceedings of SODA 2009, pp. 516\u2013524","DOI":"10.1137\/1.9781611973068.57"},{"key":"50_CR23","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/0377-2217(88)90227-5","volume":"35","author":"G. Laporte","year":"1988","unstructured":"Laporte, G., Mercure, H.: Balancing hydraulic turbine runners: A quadratic assignment problem. European Journal of Operations Research\u00a035, 378\u2013381 (1988)","journal-title":"European Journal of Operations Research"},{"key":"50_CR24","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/j.ejor.2005.09.032","volume":"176","author":"E.M. Loilola","year":"2006","unstructured":"Loilola, E.M., De Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P.M., Querido, T.: A survey for the quadratic assignment problem. Invited Review, European Journal of Operational Research\u00a0176, 657\u2013690 (2006)","journal-title":"Invited Review, European Journal of Operational Research"},{"key":"50_CR25","unstructured":"Pardalos, P., Wolkowitz, H. (eds.): Proceedings of the DIMACS Workshop on Quadratic Assignment Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a016 (1994)"},{"key":"50_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C.H. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Mathematics of Operations Research\u00a018, 1\u201311 (1993)","journal-title":"Mathematics of Operations Research"},{"key":"50_CR27","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A Parallel Repetition Theorem. SIAM Journal on Computing\u00a027, 763\u2013803 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"50_CR28","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0167-6377(86)90007-6","volume":"4","author":"M. Queyranne","year":"1986","unstructured":"Queyranne, M.: Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. Operations Research Letters\u00a04, 231\u2013234 (1986)","journal-title":"Operations Research Letters"},{"key":"50_CR29","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/1003003","volume":"3","author":"L. Steinberg","year":"1961","unstructured":"Steinberg, L.: The backboard wiring problem: a placement algorithm. SIAM Rev.\u00a03, 37\u201350 (1961)","journal-title":"SIAM Rev."},{"key":"50_CR30","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q. Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization\u00a02, 71\u2013109 (1998)","journal-title":"Journal of Combinatorial Optimization"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T08:20:34Z","timestamp":1619770834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}