{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:06:39Z","timestamp":1775282799821,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540261995","type":"print"},{"value":"9783540321026","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11496915_12","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T16:40:39Z","timestamp":1279125639000},"page":"152-166","source":"Crossref","is-referenced-by-count":8,"title":["Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut\u00a0and Graph Coloring"],"prefix":"10.1007","author":[{"given":"G.","family":"Iyengar","sequence":"first","affiliation":[]},{"given":"D. J.","family":"Phillips","sequence":"additional","affiliation":[]},{"given":"C.","family":"Stein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"12_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim.\u00a05(1), 13\u201351 (1995)","journal-title":"SIAM J. Optim."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitionings. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"issue":"2","key":"12_CR3","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"S.J. Benson","year":"2000","unstructured":"Benson, S.J., Ye, Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim.\u00a010(2), 443\u2013461 (2000) (electronic)","journal-title":"SIAM J. Optim."},{"key":"12_CR4","series-title":"International Series in Operations Research & Management Science","volume-title":"Potential function methods for approximately solving linear programming problems: theory and practice","author":"D. Bienstock","year":"2002","unstructured":"Bienstock, D.: Potential function methods for approximately solving linear programming problems: theory and practice. International Series in Operations Research & Management Science, vol.\u00a053. Kluwer Academic Publishers, Boston (2002)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Bienstock, D., Iyengar, G.: Solving fractional packing problems in ${O}^{*}(\\frac{1}{\\epsilon})$ iterations. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 146\u2013155 (2004)","DOI":"10.1145\/1007352.1007382"},{"issue":"3-4","key":"12_CR6","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1080\/10556780108805818","volume":"15","author":"S. Burer","year":"2001","unstructured":"Burer, S., Monteiro, R.D.C.: A projected gradient algorithm for solving the maxcut SDP relaxation. Optim. Methods Softw.\u00a015(3-4), 175\u2013200 (2001)","journal-title":"Optim. Methods Softw."},{"key":"12_CR7","unstructured":"Fleischer, L.: Fast approximation algorithms for fractional covering problems with box constraint. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (2004)"},{"issue":"4","key":"12_CR8","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0895480199355754","volume":"13","author":"L.K. Fleischer","year":"2000","unstructured":"Fleischer, L.K.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math.\u00a013(4), 505\u2013520 (2000) (electronic)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N., Konemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"issue":"6","key":"12_CR10","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. Journal of the ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"12_CR11","series-title":"Johns Hopkins Series in the Mathematical Sciences","volume-title":"Matrix computations","author":"G.H. Golub","year":"1983","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix computations. Johns Hopkins Series in the Mathematical Sciences, vol.\u00a03. Johns Hopkins University Press, Baltimore (1983)"},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/0804004","volume":"4","author":"M.D. Grigoriadis","year":"1994","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization\u00a04(1), 86\u2013107 (1994)","journal-title":"SIAM Journal on Optimization"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230260202","volume":"26","author":"M.D. Grigoriadis","year":"1995","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: An exponential-function reduction method for block angular convex programs. Networks\u00a026, 59\u201368 (1995)","journal-title":"Networks"},{"key":"12_CR14","series-title":"North-Holland Math. Stud","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","volume-title":"Topics on perfect graphs","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Topics on perfect graphs. North-Holland Math. Stud, vol.\u00a088, pp. 325\u2013356. North-Holland, Amsterdam (1984)"},{"issue":"5","key":"12_CR15","doi-asserted-by":"publisher","first-page":"1911","DOI":"10.1137\/S0036142995280572","volume":"34","author":"M. Hochbruck","year":"1997","unstructured":"Hochbruck, M., Lubich, C.: On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal.\u00a034(5), 1911\u20131925 (1997)","journal-title":"SIAM J. Numer. Anal."},{"key":"12_CR16","unstructured":"Iyengar, G., Phillips, D.J., Stein, C.: Approximation algorithms for semidefinite packing problems with applications to maxcut and graph coloring. Technical Report TR-2004-06, Computational Optimization Research Center, Columbia University (2004), Available at http:\/\/www.corc.ieor.columbia.edu\/reports\/techreports\/tr-2004-06.pdf"},{"issue":"2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM\u00a045(2), 246\u2013265 (1998)","journal-title":"J. ACM"},{"key":"12_CR18","first-page":"338","volume-title":"Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing","author":"P. Klein","year":"1996","unstructured":"Klein, P., Lu, H.-I.: Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING. In: Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, pp. 338\u2013347. ACM, New York (1996)"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/3-540-49381-6_41","volume-title":"Algorithms and Computation","author":"P. Klein","year":"1998","unstructured":"Klein, P., Lu, H.-I.: Space-efficient approximation algorithms for MAXCUT and COLORING semidefinite programs. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol.\u00a01533, pp. 387\u2013396. Springer, Heidelberg (1998)"},{"issue":"3","key":"12_CR20","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1137\/S0097539792241175","volume":"23","author":"P. Klein","year":"1994","unstructured":"Klein, P., Plotkin, S.A., Stein, C., Tardos, \u00c9.: Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing\u00a023(3), 466\u2013487 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jcss.1995.1020","volume":"50","author":"T. Leighton","year":"1995","unstructured":"Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, \u00c9., Tragoudas, S.: Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences\u00a050, 228\u2013243 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"12_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory\u00a025(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"4","key":"12_CR23","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1137\/1020098","volume":"20","author":"C. Moler","year":"1978","unstructured":"Moler, C., Van Loan, C.: Nineteen dubious ways to compute the exponential of a matrix. SIAM Rev.\u00a020(4), 801\u2013836 (1978)","journal-title":"SIAM Rev."},{"issue":"1","key":"12_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1137\/S00361445024180","volume":"45","author":"C. Moler","year":"2003","unstructured":"Moler, C., Van Loan, C.: Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Rev.\u00a045(1), 3\u201349 (2003)","journal-title":"SIAM Rev."},{"key":"12_CR25","unstructured":"Nesterov, Y.: Smooth minimization of nonsmooth functions. Technical report, CORE DP (2003)"},{"key":"12_CR26","series-title":"SIAM Studies in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-point polynomial algorithms in convex programming","author":"Y. Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovski, A.: Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, vol.\u00a013. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1994)"},{"key":"12_CR27","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S. Plotkin","year":"1995","unstructured":"Plotkin, S., Shmoys, D.B., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research\u00a020, 257\u2013301 (1995)","journal-title":"Mathematics of Operations Research"},{"key":"12_CR28","unstructured":"Radzik, T.: Fast deterministic approximation for the multicommodity flow problem. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 486\u2013496 (1995)"},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1145\/77600.77620","volume":"37","author":"F. Shahrokhi","year":"1990","unstructured":"Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. Journal of the ACM\u00a037, 318\u2013334 (1990)","journal-title":"Journal of the ACM"},{"issue":"2","key":"12_CR30","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M. Skutella","year":"2001","unstructured":"Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. Journal of the ACM\u00a048(2), 206\u2013242 (2001)","journal-title":"Journal of the ACM"},{"key":"12_CR31","unstructured":"van den Eshof, J., Hochbruck, M.: Preconditioning lanczos approximations to the matrix exponential. To appear in SIAM J. of Sci. Comp. (2004)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11496915_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:00:27Z","timestamp":1605643227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11496915_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540261995","9783540321026"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11496915_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}