{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:41:59Z","timestamp":1725511319099},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540005803"},{"type":"electronic","value":"9783540364788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36478-1_9","type":"book-chapter","created":{"date-parts":[[2007,10,20]],"date-time":"2007-10-20T14:33:12Z","timestamp":1192890792000},"page":"78-88","source":"Crossref","is-referenced-by-count":1,"title":["The Bundle Method for Hard Combinatorial Optimization Problems"],"prefix":"10.1007","author":[{"given":"Gerald","family":"Gruber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franz","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,1,30]]},"reference":[{"issue":"3","key":"9_CR1","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F. Barahona","year":"1983","unstructured":"F. Barahona. The max-cut problem on graphs not contractible to K 5. Operations Research Letters, 2(3):107\u2013111, 1983.","journal-title":"Operations Research Letters"},{"issue":"3","key":"9_CR2","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s101070050002","volume":"87","author":"F. Barahona","year":"2000","unstructured":"F. Barahona and R. Anbil. The volume algorithm: producing primal solutions with a subgradient method. Mathematical Programming, 87(3):385\u2013399, 2000.","journal-title":"Mathematical Programming"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"F. Barahona and A. R. Mahjoub. On the cut polytope. Mathematical Programming, 36:157\u2013173, 1986.","journal-title":"Mathematical Programming"},{"issue":"2","key":"9_CR4","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"S. J. Benson","year":"2000","unstructured":"S. J. Benson, Y. Ye, and X. Zhang. Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim., 10(2):443\u2013461 (electronic), 2000.","journal-title":"SIAM J. Optim."},{"issue":"3","key":"9_CR5","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C. Delorme","year":"1993","unstructured":"C. Delorme and S. Poljak. Laplacian eigenvalues and the maximum cut problem. Mathematical Programming, 62(3):557\u2013574, 1993.","journal-title":"Mathematical Programming"},{"issue":"1\u20133","key":"9_CR6","first-page":"143","volume":"79","author":"M. X. Goemans","year":"1997","unstructured":"M. X. Goemans. Semidefinite programming in combinatorial optimization. Mathematical Programming, 79(1\u20133):143\u2013161, 1997.","journal-title":"Mathematical Programming"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"M. X. Goemans and D. P. Williamson..878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422\u2013431, Montr\u00e9al, Qu\u00e9bec, Canada, 1994.","DOI":"10.1145\/195058.195216"},{"issue":"6","key":"9_CR8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. X. Goemans","year":"1995","unstructured":"M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115\u20131145, 1995. preliminary version, see [7].","journal-title":"Journal of the ACM"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BF02591727","volume":"29","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"M. Gr\u00f6tschel and G. L. Nemhauser. A polynomial algorithm for the max-cut problem on graphs without long odd cycles. Mathematical Programming, 29:28\u201340, 1984.","journal-title":"Mathematical Programming"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. Hadlock","year":"1975","unstructured":"F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4:221\u2013225, 1975.","journal-title":"SIAM Journal on Computing"},{"key":"9_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/3-540-69346-7_32","volume-title":"Integer Programming and Combinatorial Optimization","author":"C. Helmberg","year":"1998","unstructured":"C. Helmberg, K. C. Kiwiel, and F. Rendl. Incorporating inequality constraints in the spectral bundle method. In R. E. Bixby, E. A. Boyd, and R. Z. R\u00edos-Mercado, editors, Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pages 423\u2013435. Springer, 1998."},{"issue":"3","key":"9_CR12","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C. Helmberg","year":"2000","unstructured":"C. Helmberg and F. Rendl. A spectral bundle method for semidefinite programming. SIAM Journal on Optimization, 10(3):673\u2013696, 2000.","journal-title":"SIAM Journal on Optimization"},{"issue":"2","key":"9_CR13","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1137\/0806020","volume":"6","author":"C. Helmberg","year":"1996","unstructured":"C. Helmberg, F. Rendl, R. J. Vanderbei, and H. Wolkowicz. An interior point method for semidefinite programming. SIAM Journal on Optimization, 6(2):342\u2013361, 1996.","journal-title":"SIAM Journal on Optimization"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Some optimal inapproximability results. In Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), pages 1\u201310, 1997.","DOI":"10.1145\/258533.258536"},{"issue":"2","key":"9_CR15","first-page":"127","volume":"44","author":"M. J\u00fcnger","year":"1989","unstructured":"M. J\u00fcnger, F. Barahona, and G. Reinelt. Experiments in quadratic 0-1 programming. Mathematical Programming, 44(2):127\u2013137, 1989.","journal-title":"Mathematical Programming"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103, New York, 1972. Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"9_CR17","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R. M. Karp","year":"1975","unstructured":"R. M. Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45\u201368, 1975.","journal-title":"Networks"},{"key":"9_CR18","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0074500","volume-title":"Methods of Descent of Nondifferentiable Optimization","author":"K. C. Kiwiel","year":"1985","unstructured":"K. C. Kiwiel. Methods of Descent of Nondifferentiable Optimization, volume 1133 of Lecture Notes in Mathematics. Springer, Berlin, 1985."},{"key":"9_CR19","first-page":"263","volume":"6","author":"K. C. Kiwiel","year":"1989","unstructured":"K. C. Kiwiel. Survey of bundle methods for nondifferentiable optimization. Math. Appl. Jan. Ser.6, 6:263\u2013282, 1989.","journal-title":"Math. Appl. Jan. Ser.6"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF01585731","volume":"46","author":"K. C. Kiwiel","year":"1990","unstructured":"K. C. Kiwiel. Proximity control in bundle methods for convex nondifferentiable minimization. Mathematical Programming, 46:105\u2013122, 1990.","journal-title":"Mathematical Programming"},{"key":"9_CR21","unstructured":"C. Lemarechal. Bundle methods in nonsmooth optimization. In Claude Lemarechal and Robert Mifflin, editors, Proceedings of the IIASA Workshop, vol. 3, Nonsmooth Optimization, March 28\u2013April 8, pages 79\u2013102. Pergamon Press, 1978, 1977."},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01585555","volume":"69","author":"C. Lemar\u00e9chal","year":"1995","unstructured":"C. Lemar\u00e9chal, A. Nemirovskii, and Yu. Nesterov. New variants of bundle methods. Mathematical Programming, 69:111\u2013147, 1995.","journal-title":"Mathematical Programming"},{"key":"9_CR23","unstructured":"L. Lov\u00e1sz. Semidefinite programs and combinatorial optimization. Lecture Notes, 1995."},{"issue":"2","key":"9_CR24","first-page":"225","volume":"77","author":"M. Laurent","year":"1997","unstructured":"M. Laurent, S. Poljak, F. Rendl. Connections between semidefinite relaxations of the max-cut and stable set problems. Mathematical Programming, 77(2):225\u2013246, 1997.","journal-title":"Mathematical Programming"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"B. Mohar and S. Poljak. Eigenvalues in combinatorial optimization. In Combinatorial Graph-Theoretical Problems in Linear Algebra, IMA Vol. 50. Springer-Verlag, 1993.","DOI":"10.1007\/978-1-4613-8354-3_5"},{"issue":"3","key":"9_CR26","first-page":"502","volume":"10","author":"G. I. Orlova","year":"1972","unstructured":"G. I. Orlova and Ya.G. Dorfman. Finding the maximum cut in a graph. Engineering Cybernetics, 10(3):502\u2013506, 1972.","journal-title":"Engineering Cybernetics"},{"key":"9_CR27","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF02238072","volume":"52","author":"S. Poljak","year":"1994","unstructured":"S. Poljak and F. Rendl. Node and edge relaxations for the max-cut problem. Computing, 52:123\u2013127, 1994.","journal-title":"Computing"},{"issue":"3","key":"9_CR28","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0805024","volume":"5","author":"S. Poljak","year":"1995","unstructured":"S. Poljak and F. Rendl. Nonpolyhedral relaxations of graph-bisection problems. SIAM Journal on Optimization, 5(3):467\u2013487, 1995.","journal-title":"SIAM Journal on Optimization"},{"key":"9_CR29","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0168-9274(98)00097-X","volume":"29","author":"F. Rendl","year":"1999","unstructured":"F. Rendl. Semidefinite programming and combinatorial optimization. Applied Numerical Mathematics, 29:255\u2013281, 1999.","journal-title":"Applied Numerical Mathematics"},{"key":"9_CR30","series-title":"Princeton Mathematics Series","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"R. T. Rockafellar","year":"1970","unstructured":"R. Tyrrell Rockafellar. Convex Analysis, volume 28 of Princeton Mathematics Series. Princeton University Press, Princeton, 1970."},{"key":"9_CR31","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1137\/0802008","volume":"2","author":"H. Schramm","year":"1992","unstructured":"H. Schramm and J. Zowe. A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results. SIAM J. Optim., 2:121\u2013152, 1992.","journal-title":"SIAM J. Optim."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization \u2014 Eureka, You Shrink!"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36478-1_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:02:39Z","timestamp":1556920959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36478-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540005803","9783540364788"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-36478-1_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}