{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:25:23Z","timestamp":1725549923115},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_74","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T08:46:24Z","timestamp":1128588384000},"page":"839-849","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"74_CR1","first-page":"534","volume-title":"Proc. 34th STOC","author":"N. Alon","year":"2002","unstructured":"Alon, N., de la Vega, W.F., Kannan, R., Karpinski, M.: Random Sampling and Approximation of MAX-CSP Problems. In: Proc. 34th STOC, pp. 534\u2013543. ACM, New York (2002); The full paper can be found in Technical Report TR01-100, ECCC (2001)"},{"key":"74_CR2","unstructured":"Arora, S., Berger, E., Hazan, E., Kindler, G., Safra, M.: On Non-Approximability for Quadratic Programs. Technical Report TR05-58, ECCC, 2005. To appear at Proc. 46th FOCS, IEEE (2005)"},{"key":"74_CR3","first-page":"284","volume-title":"Proc. 27th STOC","author":"S. Arora","year":"1995","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. In: Proc. 27th STOC, pp. 284\u2013293. ACM, New York (1995)"},{"key":"74_CR4","first-page":"14","volume-title":"Proc. 33rd FOCS","author":"S. Arora","year":"1992","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. In: Proc. 33rd FOCS, pp. 14\u201323. IEEE, Los Alamitos (1992)"},{"key":"74_CR5","volume-title":"Algebraic Graph Theory","author":"N. Biggs","year":"1996","unstructured":"Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1996); ISBN 0-521-45897-8"},{"issue":"3","key":"74_CR6","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U","volume":"8","author":"W.F. Vega de la","year":"1996","unstructured":"de la Vega, W.F.: MAX-CUT has a Randomized Approximation Scheme in Dense Graphs. Random Structures and Algorithms\u00a08(3), 187\u2013198 (1996)","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"74_CR7","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1002\/1098-2418(200007)16:4<314::AID-RSA2>3.0.CO;2-E","volume":"16","author":"W.F. Vega de la","year":"2000","unstructured":"de la Vega, W.F., Karpinski, M.: Polynomial time approximation of dense weighted instances of MAX-CUT. Random Structures and Algorithms\u00a016(4), 314\u2013332 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"74_CR8","unstructured":"de la Vega, W.F., Karpinski, M.: A Polynomial Time Approximation Scheme for Subdense MAX-CUT. Technical Report TR02-044, ECCC (2002)"},{"key":"74_CR9","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM\u00a042, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"74_CR10","first-page":"339","volume-title":"Proc. 37th FOCS","author":"O. Goldreich","year":"1996","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property Testing and its Connection to Learning and Approximation. In: Proc. 37th FOCS, vol.\u00a045, pp. 339\u2013348. IEEE, Los Alamitos (1996); The full paper can be found in J. ACM 45, 653\u2013750 (1998)"},{"key":"74_CR11","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins Universal Press, Baltimore (1996); ISBN 0-8018-5414-8","edition":"3"},{"key":"74_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4844-2","volume-title":"Linear Programming","author":"H. Karloff","year":"1991","unstructured":"Karloff, H.: Linear Programming. Birkh\u00e4user, Boston (1991); ISBN 3-7643-3561-0"},{"key":"74_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"74_CR14","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximate packing integer programs. J. Comput. System Sci.\u00a037(2), 130\u2013143 (1988)","journal-title":"J. Comput. System Sci."},{"key":"74_CR15","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.: Randomized Rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_74.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:13:38Z","timestamp":1619493218000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11561071_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}