{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,29]],"date-time":"2024-03-29T23:30:33Z","timestamp":1711755033479},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T00:00:00Z","timestamp":1096588800000},"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":[[2005,4]]},"DOI":"10.1007\/s101070100246","type":"journal-article","created":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T01:57:57Z","timestamp":1096595877000},"page":"577-588","source":"Crossref","is-referenced-by-count":8,"title":["Strengthening the Lov\ufffdsz bound for graph coloring"],"prefix":"10.1007","volume":"102","author":[{"given":"Philippe","family":"Meurdesoif","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2004,10,1]]},"reference":[{"key":"CRAlizadeh97","doi-asserted-by":"crossref","unstructured":"Alizadeh, F., Haeberly, J.-P., Nayakkankuppam, M.V., Overton, M.L. (1997): SDPPack User?s Guide, version 0.8 beta. Technical report, NYU Computer Science Dpt, March 1997. URL: http:\/\/www.cs.nyu.edu\/phd_students\/madhu\/sdppack\/sdppack.html","DOI":"10.1007\/BF02614432"},{"key":"CRAlon94","doi-asserted-by":"crossref","unstructured":"Alon, N. (1994): Explicit Ramsey graphs and orthonormal labelings. Electron. J. Comb. 1, # R12","DOI":"10.37236\/1192"},{"key":"CRAlonKahale94","first-page":"253","volume":"80","author":"Alon","year":"1998","unstructured":"Alon, N., Kahale, N. (1998): Approximating the independence number via the ?-function. Math. Program. 80, 253?264","journal-title":"Math. Program."},{"key":"CRFeige96","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J. (1996): Zero Knowledge and the Chromatic Number. In: Proceedings of the 11th Annual IEEE Conference in Computing Complexity (preliminary version), pp. 278?287","DOI":"10.1109\/CCC.1996.507690"},{"key":"CRFrieze95","doi-asserted-by":"crossref","unstructured":"Frieze, A., Jerrum, M. (1995): Improved approximation algorithms for MAX k-cut and MAX BISECTION. In: Proceedings of the Fourth MPS Conference on Integer Programming and Combinatorial Optimization. Springer","DOI":"10.1007\/3-540-59408-6_37"},{"key":"CRGoemans95","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P. (1995): Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42, 1115?1145","journal-title":"J. ACM"},{"key":"CRHorn85","doi-asserted-by":"crossref","unstructured":"Horn, R.A., Johnson, C.R. (1985): Matrix Analysis. Cambridge University Press, Cambridge (reedited 1999)","DOI":"10.1017\/CBO9780511810817"},{"key":"CRJensen95","unstructured":"Jensen, T.R., Toft, B. (1995): Graph coloring problems. Wiley-Interscience series in discrete mathematics and optimization. Wiley, New York"},{"key":"CRKarger98","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"Karger","year":"1998","unstructured":"Karger, D., Motwani, R., Sudan, M. (1998): Approximate graph coloring by semidefinite programming. J. ACM 45 (2), 246?265, March 1998","journal-title":"J. ACM"},{"key":"CRKnuth94","doi-asserted-by":"crossref","unstructured":"Knuth, D. (1994): The Sandwich Theorem. Electron. J. Comb. 1, # A1, 48 pp.","DOI":"10.37236\/1193"},{"key":"CRLemarechal00","unstructured":"Lemar\u00e9chal, C., Oustry, F. (1999): Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization. Rapport de Recherche Nr. 3710. Inria"},{"key":"CRLovasz79","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L. (1979): On the Shannon Capacity of a Graph. IEEE Trans. Inf. Theory IT-25 (1), 1?7","DOI":"10.1109\/TIT.1979.1055985"},{"key":"CRLund94","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M. (1994): On the hardness of approximating minimization problems. J. ACM 41 (5), 960?981","journal-title":"J. ACM"},{"key":"CRMcEliece78","first-page":"134","volume":"3","author":"McEliece","year":"1978","unstructured":"McEliece, R.J., Rodemich, E.R., Rumsey Jr., H.C. (1978): The Lov\u00e1sz Bound and Some Generalizations. J. Comb. Inf. Syst. Sci. 3 (3), 134?152","journal-title":"J. Comb. Inf. Syst. Sci."},{"key":"CRPoljak95","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01100205","volume":"7","author":"Poljak","year":"1995","unstructured":"Poljak, S., Rendl, F., Wolkowicz, H. (1995): A recipe for semidefinite relaxation for (0?1)-quadratic programming. J. Glob. Optim. 7, 51?73","journal-title":"J. Glob. Optim."},{"key":"CRSchrijver79","doi-asserted-by":"crossref","unstructured":"Schrijver, A. (1979): A Comparison of the Delsarte and Lov\u00e1sz Bounds. IEEE Trans. Inf. Theory IT-25 (4), 425?429","DOI":"10.1109\/TIT.1979.1056072"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s101070100246.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s101070100246\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s101070100246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T07:37:02Z","timestamp":1585899422000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s101070100246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10,1]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,4]]}},"alternative-id":["246"],"URL":"https:\/\/doi.org\/10.1007\/s101070100246","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,10,1]]}}}