{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T15:40:15Z","timestamp":1777477215783,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,6,14]],"date-time":"2007-06-14T00:00:00Z","timestamp":1181779200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2008,9]]},"DOI":"10.1007\/s10107-007-0139-z","type":"journal-article","created":{"date-parts":[[2007,6,14]],"date-time":"2007-06-14T06:14:17Z","timestamp":1181801657000},"page":"65-72","source":"Crossref","is-referenced-by-count":18,"title":["The capacitated max k-cut problem"],"prefix":"10.1007","volume":"115","author":[{"given":"Daya Ram","family":"Gaur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramesh","family":"Krishnamurti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Kohli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,14]]},"reference":[{"key":"139_CR1","doi-asserted-by":"crossref","unstructured":"Ageev, A.A., Sviridenko, M.I.: An approximation algorithm for hypergraph max k-cut with given sizes of parts. Lecture Notes in Computer Science (Proceedings of ESA \u201900), vol. 1879, pp. 32\u201341 (2000)","DOI":"10.1007\/3-540-45253-2_4"},{"issue":"2","key":"139_CR2","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). A 0.5-approximation algorithm for max dicut with given sizes of parts. SIAM J. Discret. Math. 14(2): 246\u2013255","journal-title":"SIAM J. Discret. Math."},{"key":"139_CR3","doi-asserted-by":"crossref","unstructured":"Andersson, G.: An approximation algorithm for max p-section. Lecture Notes in Computer Science (Proceedings of STACS\u201999), vol. 1563, pp. 237\u2013247 (1999)","DOI":"10.1007\/3-540-49116-3_22"},{"key":"139_CR4","first-page":"457","volume":"90","author":"A. Aslidis","year":"1990","unstructured":"Aslidis A. (1990). Minimizing of overstowage in container ship operations. Oper. Res. 90: 457\u2013471","journal-title":"Oper. Res."},{"key":"139_CR5","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0360-8352(93)90273-Z","volume":"25","author":"M. Avriel","year":"1993","unstructured":"Avriel M. and Penn M. (1993). Exact and approximate solutions of the container ship stowage problem. Comput. Ind. Eng. 25: 271\u2013274","journal-title":"Comput. Ind. Eng."},{"key":"139_CR6","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1023\/A:1018956823693","volume":"76","author":"M. Avriel","year":"1997","unstructured":"Avriel M., Penn M., Shpirer N. and Witteboon S. (1997). Stowage planning for container ships to reduce the number of shifts. Ann. Oper. Res. 76: 55\u201371","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"139_CR7","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1287\/opre.1030.0083","volume":"52","author":"S. Bollapragada","year":"2004","unstructured":"Bollapragada S. and Garbiras M. (2004). Scheduling commercials on broadcast television. Oper. Res. 52(3): 337\u2013345","journal-title":"Oper. Res."},{"issue":"3","key":"139_CR8","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1023\/B:JOCO.0000038911.67280.3f","volume":"8","author":"E. de Klerk","year":"2004","unstructured":"de Klerk E., Pasechnik D.V. and Warners J.P. (2004). On approximate graph colouring and MAX k-CUT algorithms based on the \u03b8-function. J. Comb. Optim. 8(3): 267\u2013294","journal-title":"J. Comb. Optim."},{"key":"139_CR9","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U. Feige","year":"2001","unstructured":"Feige U. and Langberg M. (2001). Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41: 174\u2013211","journal-title":"J. Algorithms"},{"issue":"1","key":"139_CR10","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(1): 67\u201381","journal-title":"Algorithmica"},{"key":"139_CR11","doi-asserted-by":"crossref","unstructured":"Gaur, D., Krishnamurti, R.: The capacitated max k-cut problem. In: Proceedings of the International Conference on Computational Science and its Applications (2005), LNCS 3483, pp. 670\u2013679","DOI":"10.1007\/11424925_71"},{"key":"139_CR12","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. J. Assoc. Comput. Mach. 42: 1115\u20131145","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"139_CR13","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/j.jcss.2003.07.012","volume":"68","author":"M.X. Goemans","year":"2004","unstructured":"Goemans M.X. and Williamson D.P. (2004). Approximation algorithms for MAX 3-CUT and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2): 442\u2013470","journal-title":"J. Comput. Syst. Sci."},{"key":"139_CR14","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"Johnson D.S., Papadimitriou C.H. and Yannakakis M. (1988). How easy is local search?. J. Comput. Syst. Sci. 37: 79\u2013100","journal-title":"J. Comput. Syst. Sci."},{"key":"139_CR15","unstructured":"Karloff, H.J.: Fast parallel algorithms for graph-theoretic problems: matching, coloring and partitioning. Ph.D. Thesis, UC Berkeley (1985)"},{"key":"139_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.1997.002","volume":"2","author":"V. Kann","year":"1997","unstructured":"Kann V., Khanna S., Lagergren J. and Panconesi A. (1997). On the hardness of approximating max k-cut and its dual. Chicago J. Theor. Comput. Sci. 2: 1\u201318","journal-title":"Chicago J. Theor. Comput. Sci."},{"issue":"5","key":"139_CR17","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1137\/S0097539703431007","volume":"33","author":"J.B. Orlin","year":"2004","unstructured":"Orlin J.B., Punnen A.P. and Schulz A.S. (2004). Approximate local search in combinatorial optimization. SIAM J. Comput. 33(5): 1201\u20131214","journal-title":"SIAM J. Comput."},{"key":"139_CR18","volume-title":"Combinatorial optimization: algorithms and complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou C.H. and Steiglitz K. (1982). Combinatorial optimization: algorithms and complexity. Prentice-Hall, Englewood Cliffs"},{"key":"139_CR19","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. (A) 90: 101\u2013111","journal-title":"Math. Program. (A)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0139-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-007-0139-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0139-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:50:04Z","timestamp":1559123404000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-007-0139-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,14]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["139"],"URL":"https:\/\/doi.org\/10.1007\/s10107-007-0139-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,14]]}}}