{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,18]],"date-time":"2026-10-18T01:17:40Z","timestamp":1792286260335,"version":"4.4.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,5,1]],"date-time":"1997-05-01T00:00:00Z","timestamp":862444800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1997,5,1]],"date-time":"1997-05-01T00:00:00Z","timestamp":862444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,5]]},"DOI":"10.1007\/bf02523688","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T05:02:35Z","timestamp":1162962155000},"page":"67-81","source":"Crossref","is-referenced-by-count":291,"title":["Improved approximation algorithms for MAXk-CUT and MAX BISECTION"],"prefix":"10.1007","volume":"18","author":[{"given":"A.","family":"Frieze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02523688_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimisation,SIAM Journal on Optimization\n                           5 (1995), 13\u201351.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02523688_CR2","series-title":"Proceedings of the 27th Annual ACM Symposium on Theory of Computing","first-page":"284","volume-title":"Polynomial time approximation schemes for dense instances of NP-hard problem","author":"S. Arora","year":"1995","unstructured":"S. Arora, D. Karger, and M. Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problem,Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1995, pp. 284\u2013293."},{"key":"BF02523688_CR3","series-title":"Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science","first-page":"14","volume-title":"Proof verification and hardness of approximation problems","author":"S. Arora","year":"1992","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems,Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, New York, 1992, pp. 14\u201323."},{"key":"BF02523688_CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1111\/j.1467-842X.1965.tb00033.x","volume":"7","author":"E. Bofinger","year":"1965","unstructured":"E. Bofinger and V. J. Bofinger, The correlation of maxima in samples drawn from a bivariate normal distribution,The Australian Journal of Statistics\n                           7 (1965), 57\u201361.","journal-title":"The Australian Journal of Statistics"},{"key":"BF02523688_CR5","volume-title":"Order Statistics","author":"H. A. David","year":"1980","unstructured":"H. A. David,Order Statistics, Wiley, New York, 1980."},{"key":"BF02523688_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. de la Vega","year":"1996","unstructured":"W. F. de la Vega, MAXCUT has a randomized approximation scheme in dense graphs,Random Structures and Algorithms\n                           8 (1996), 187\u2013198.","journal-title":"Random Structures and Algorithms"},{"key":"BF02523688_CR7","volume-title":"The Asymptotic Theory of Extreme Order Statistics","author":"J. Galambos","year":"1978","unstructured":"J. Galambos,The Asymptotic Theory of Extreme Order Statistics, Wiley, New York, 1978."},{"key":"BF02523688_CR8","series-title":"Proceedings of the 26th Annual ACM Symposium on Theory of Computing","first-page":"422","volume-title":"878-Approximation algorithms for MAXCUT and MAX2SAT","author":"M. X. Goemans","year":"1994","unstructured":"M. X. Goemans and D. P. Williamson, 878-Approximation algorithms for MAXCUT and MAX2SAT,Proceedings of the 26th Annual ACM Symposium on Theory of Computing, ACM Press, 1994, New York, pp. 422\u2013431."},{"key":"BF02523688_CR9","series-title":"Technical Report TRITA-NA-9505","volume-title":"On the hardness of approximating MAX k-CUT and its dual","author":"V. Kann","year":"1995","unstructured":"V. Kann, S. Khanna, J. Lagergren, and A. Panconesi, On the hardness of approximating MAX k-CUT and its dual, Technical Report TRITA-NA-9505, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1995."},{"key":"BF02523688_CR10","series-title":"Proceedings of the 35th IEEE Symposium on Foundations of Computer Science","first-page":"2","volume-title":"Approximate graph coloring by semidefinite programming","author":"D. Karger","year":"1994","unstructured":"D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming,Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, New York, 1994, pp. 2\u201313."},{"key":"BF02523688_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes,Journal of Computer and System Sciences\n                           43 (1991), 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02523688_CR12","volume-title":"Orthogonal Functions","author":"G. Sansone","year":"1959","unstructured":"G. Sansone,Orthogonal Functions (translated from the Italian by A. H. Diamond), Interscience, New York, 1959."},{"key":"BF02523688_CR13","volume-title":"The Theory of Functions","author":"E. C. Titchmarsh","year":"1939","unstructured":"E. C. Titchmarsh,The Theory of Functions (second edition), Oxford University Press, Oxford, 1939.","edition":"second edition"},{"key":"BF02523688_CR14","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1112\/jlms\/s1-8.3.194","volume":"8","author":"G. N. Watson","year":"1933","unstructured":"G. N. Watson, Notes on generating functions of polynomials: Hermite polynomials,Journal of the London Mathematical Society\n                           8 (1933), 194\u2013199.","journal-title":"Journal of the London Mathematical Society"},{"key":"BF02523688_CR15","series-title":"London Mathematical Society Lecture Notes","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: Knots, Colourings and Counting","author":"D. J. A. Welsh","year":"1993","unstructured":"D. J. A. Welsh,Complexity: Knots, Colourings and Counting, London Mathematical Society Lecture Notes, volume 186, Cambridge University Press, Cambridge, 1993."},{"key":"BF02523688_CR16","series-title":"Mathematical Programming Study","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume-title":"Combinatorial Optimization II","author":"L. A. Wolsey","year":"1980","unstructured":"L. A. Wolsey, Heuristic analysis, linear programming and branch and bound, inCombinatorial Optimization II, Mathematical Programming Study, volume 13, North-Holland, Amsterdam, 1980, pp. 121\u2013134."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523688.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02523688\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523688.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,15]],"date-time":"2022-05-15T01:19:17Z","timestamp":1652577557000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02523688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,5]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,5]]}},"alternative-id":["BF02523688"],"URL":"https:\/\/doi.org\/10.1007\/bf02523688","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,5]]}}}