{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:10:39Z","timestamp":1751429439145,"version":"3.41.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2003,12,1]],"date-time":"2003-12-01T00:00:00Z","timestamp":1070236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,12,1]],"date-time":"2003-12-01T00:00:00Z","timestamp":1070236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Global Optimization"],"published-print":{"date-parts":[[2003,12]]},"DOI":"10.1023\/a:1026094110647","type":"journal-article","created":{"date-parts":[[2003,10,24]],"date-time":"2003-10-24T23:17:50Z","timestamp":1067037470000},"page":"399-410","source":"Crossref","is-referenced-by-count":9,"title":["Improved Approximation Algorithms for MAX \n$$\\frac{n}{{\\text{2}}}$$\n-DIRECTED-BISECTION and MAX \n$$\\frac{n}{{\\text{2}}}$$\n-DENSE-SUBGRAPH"],"prefix":"10.1007","volume":"27","author":[{"given":"Dachuan","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiye","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenghai","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liping","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5125118_CR1","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1137\/S089548010036813X","volume":"14","author":"A. Ageev","year":"2001","unstructured":"Ageev, A., Hassin, R., and Sviridenko M. (2001), An 0.5-approximation algorithm for the max dicut with given sizes of parts, SIAM J. Discrete Math. 14, 246\u2013255.","journal-title":"SIAM J. Discrete Math."},{"key":"5125118_CR2","doi-asserted-by":"crossref","unstructured":"Bertsimas, D. and Ye, Y. (1998), Semidefinite relaxations, multivariate normal distributions, and order statistics. In: Du, D. Z. and Pardalos, P.M. (eds.), Handbook of Combinatorial Optimization (Vol. 3), pp. 1\u201319, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4613-0303-9_24"},{"key":"5125118_CR3","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1109\/ISTCS.1995.377033","volume-title":"Proceedings of the 3rd Israel Symposium on Theory and Computing Systems","author":"U. Feige","year":"1995","unstructured":"Feige, U. and Goemans, M. X. (1995), Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In: Proceedings of the 3rd Israel Symposium on Theory and Computing Systems, Tel Aviv, Israel, pp. 182\u2013189."},{"key":"5125118_CR4","unstructured":"Feige, U. and Langberg, M. (1999), Approximation algorithms for maximization problems arising in graph partitioning, Manuscript and M. Sc. thesis."},{"key":"5125118_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A. Frieze","year":"1997","unstructured":"Frieze, A. and Jerrum, M. (1997), Improved approximation algorithms for max k-cut and max bisection, Algorithmica 18, 67-81.","journal-title":"Algorithmica"},{"key":"5125118_CR6","series-title":"Technical Report, Department of Applied Mathematics and Computer Science","volume-title":"On the densest k-subgraph problem","author":"U. Feige","year":"1997","unstructured":"Feige, U. and Seltser, M. (1997), On the densest k-subgraph problem, Technical Report, Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot."},{"key":"5125118_CR7","unstructured":"Goemans, M. X. (1996), Mathematical programming and approximation algorithms, Lecture given at the Summer School on Approximate Solution of Hard Combinatorial Problems, Udine."},{"key":"5125118_CR8","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. X. Goemans","year":"1995","unstructured":"Goemans, M. X. and Williamson, D. P. (1995), Improved approximation algorithms for Maximum Cut and Satisfiability problems using semidefinite programming, Journal of ACM 42, 1115\u20131145.","journal-title":"Journal of ACM"},{"key":"5125118_CR9","doi-asserted-by":"crossref","unstructured":"Halperin, E. and Zwick, U. (2001), A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Manuscript.","DOI":"10.1007\/3-540-45535-3_17"},{"key":"5125118_CR10","doi-asserted-by":"crossref","unstructured":"Han, Q., Ye, Y., Zhang, H., and Zhang, J. (2002), On approximation of Max-Vertex-Cover, to appear in European Journal of Operational Research.","DOI":"10.1016\/S0377-2217(02)00330-2"},{"key":"5125118_CR11","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/s101070100288","volume":"92","author":"Q. Han","year":"2002","unstructured":"Han, Q., Ye, Y., and Zhang, J. (2002), An improved rounding method and semidefinite programming relaxation for graph partition, Math. Program. 92, 509\u2013535.","journal-title":"Math. Program."},{"key":"5125118_CR12","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lovasz","year":"1990","unstructured":"Lovasz, L. and Shrijver, A. (1990), Cones of matrices and setfunctions, and 0-1 optimization, SIAM J. of Optimization 1, 166\u2013190.","journal-title":"SIAM J. of Optimization"},{"key":"5125118_CR13","doi-asserted-by":"crossref","first-page":"1641","DOI":"10.1137\/S0097539796309326","volume":"28","author":"S. Mahajan","year":"1999","unstructured":"Mahajan, S. and Ramesh, H. (1999), Derandomizing approximation algorithms based on semidefinite programming, SIAM J. Comput. 28, 1641\u20131663.","journal-title":"SIAM J. Comput."},{"key":"5125118_CR14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1080\/10556789808805690","volume":"9","author":"Y. Nesterov","year":"1998","unstructured":"Nesterov, Y. (1998), Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software 9, 141\u2013160.","journal-title":"Optimization Methods and Software"},{"key":"5125118_CR15","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H. and Yannakakis, M. (1991), Optimization, approximation, and complexity classes, J. Comput. Syst. Sci. 43, 425\u2013440.","journal-title":"J. Comput. Syst. Sci."},{"key":"5125118_CR16","doi-asserted-by":"crossref","unstructured":"Srivastav, A. and Wolf, K. (1998), Finding dense subgraphs with semidefinite programming. In: Jansen, K. and Rolim, J. (eds.) Approximation Algorithms for Combinatorial Optimization, pp. 181\u2013191.","DOI":"10.1007\/BFb0053974"},{"key":"5125118_CR17","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/PL00011415","volume":"90","author":"Y. Ye","year":"2001","unstructured":"Ye, Y. (2001), A.699-approximation algorithm for Max-Bisection, Math. Program. 90, 101\u2013111.","journal-title":"Math. Program."},{"key":"5125118_CR18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1023\/A:1021390231133","volume":"25","author":"Y. Ye","year":"2003","unstructured":"Ye, Y. and Zhang, J. (2003), Approximation of dense-\n$$\\frac{n}{{\\text{2}}}$$\n-subgraph and the complement of min-bisection, Journal of Global Optimization 25, 55\u201373.","journal-title":"Journal of Global Optimization"},{"key":"5125118_CR19","doi-asserted-by":"crossref","unstructured":"Zwick, U. (1999), Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In: Proceedings of the 30th Symposium on Theory of Computation (STOC), pp. 551\u2013560.","DOI":"10.1145\/301250.301431"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1026094110647.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1026094110647\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1026094110647.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:44:28Z","timestamp":1751366668000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1026094110647"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,12]]}},"alternative-id":["5125118"],"URL":"https:\/\/doi.org\/10.1023\/a:1026094110647","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}