{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T21:14:11Z","timestamp":1648761251481},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,2,13]],"date-time":"2013-02-13T00:00:00Z","timestamp":1360713600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s00453-013-9756-5","type":"journal-article","created":{"date-parts":[[2013,2,12]],"date-time":"2013-02-12T18:04:50Z","timestamp":1360692290000},"page":"605-618","source":"Crossref","is-referenced-by-count":0,"title":["An SDP Primal-Dual Algorithm for Approximating the Lov\u00e1sz-Theta Function"],"prefix":"10.1007","volume":"69","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin L.","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajiv","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,2,13]]},"reference":[{"key":"9756_CR1","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. http:\/\/www.cs.princeton.edu\/~ehazan\/papers\/MWsurvey.pdf"},{"key":"9756_CR2","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1109\/FOCS.2004.1","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science","author":"S. Arora","year":"2004","unstructured":"Arora, S., Hazan, E., Kale, S.: ${O}(\\sqrt{\\log n})$ approximation to sparsest cut in $\\tilde{O}(n^{2})$ time. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0238\u2013247 (2004)"},{"key":"9756_CR3","first-page":"227","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"S. Arora","year":"2007","unstructured":"Arora, S., Kale, S.: A combinatorial, primal-dual approach to semidefinite programs. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp.\u00a0227\u2013236 (2007)"},{"issue":"1","key":"9756_CR4","doi-asserted-by":"crossref","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. 5(1), 13\u201351 (1995)","journal-title":"SIAM J. Optim."},{"key":"9756_CR5","first-page":"114","volume":"10","author":"C. Berge","year":"1961","unstructured":"Berge, C.: F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Wiss. Z., Martin-Luther-Univ. Halle-Wittenb., Math.-Nat.wiss. Reihe 10, 114 (1961)","journal-title":"Wiss. Z., Martin-Luther-Univ. Halle-Wittenb., Math.-Nat.wiss. Reihe"},{"key":"9756_CR6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P., Vuskovi\u0107, K.: Recognizing |Berge graphs. Combinatorica 25, 143\u2013186 (2005)","journal-title":"Combinatorica"},{"key":"9756_CR7","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"9756_CR8","first-page":"517","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"F. Eisenbrand","year":"2003","unstructured":"Eisenbrand, F., Funke, S., Garg, N., K\u00f6nemann, J.: A\u00a0combinatorial algorithm for computing a maximum independent set in a t-perfect graph. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0517\u2013522 (2003)"},{"key":"9756_CR9","first-page":"300","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","author":"N. Garg","year":"1998","unstructured":"Garg, N., K\u00f6nemann, 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.\u00a0300\u2013309 (1998)"},{"key":"9756_CR10","first-page":"325","volume-title":"Annals of Discrete Mathematics","author":"L. Grotchel","year":"1984","unstructured":"Grotchel, L., Lovasz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Annals of Discrete Mathematics, pp.\u00a0325\u2013356 (1984)"},{"key":"9756_CR11","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"L. Grotchel","year":"1987","unstructured":"Grotchel, L., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1987)"},{"key":"9756_CR12","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"9756_CR13","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1996","unstructured":"Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)","edition":"3"},{"issue":"1","key":"9756_CR14","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/090762671","volume":"21","author":"G. Iyengar","year":"2011","unstructured":"Iyengar, G., Phillips, D.J., Stein, C.: Approximating semidefinite packing programs. SIAM J. Optim. 21(1), 231\u2013268 (2011)","journal-title":"SIAM J. Optim."},{"key":"9756_CR15","first-page":"338","volume-title":"Proceedings of the 28th Annual ACM Symposium on Theory of Computing","author":"P.N. Klein","year":"1996","unstructured":"Klein, P.N., Lu, H.-I.: Efficient approximation algorithms for semidefinite programs arising from max cut and coloring. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 338\u2013347 (1996)"},{"issue":"2","key":"9756_CR16","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D.R. Karger","year":"1998","unstructured":"Karger, D.R., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM 45(2), 246\u2013265 (1998)","journal-title":"J. ACM"},{"key":"9756_CR17","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: The sandwich theorem. Electron. J. Comb. 1 (1994)","DOI":"10.37236\/1193"},{"key":"9756_CR18","first-page":"494","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science","author":"C. Koufogiannakis","year":"2007","unstructured":"Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0494\u2013504 (2007)"},{"key":"9756_CR19","doi-asserted-by":"crossref","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. Inf. Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9756_CR20","first-page":"235","volume-title":"Proceedings of the 1996 IEEE International Symposium on Computer-Aided Control System Design","author":"M.V. Nayakkankuppam","year":"1996","unstructured":"Nayakkankuppam, M.V., Overton, M.L.: Primal-dual interior-point methods for semidefinite programming: numerical experience with block-diagonal problems. In: Proceedings of the 1996 IEEE International Symposium on Computer-Aided Control System Design, pp.\u00a0235\u2013239 (1996)"},{"key":"9756_CR21","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1145\/301250.301389","volume-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing","author":"V.Y. Pan","year":"1999","unstructured":"Pan, V.Y., Chen, Z.Q.: The complexity of the matrix eigenproblem. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC \u201999, pp.\u00a0507\u2013516. ACM, New York (1999)"},{"key":"9756_CR22","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/SFCS.1991.185411","volume-title":"Proceedings of the 32nd Annual Symposium on Foundations of Computer Science","author":"S.A. Plotkin","year":"1991","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pp.\u00a0495\u2013504 (1991)"},{"key":"9756_CR23","first-page":"69","volume":"109","author":"P. Seymour","year":"2006","unstructured":"Seymour, P.: How the proof of the strong perfect graph conjecture was found. Gaz. Math. 109, 69\u201383 (2006)","journal-title":"Gaz. Math."},{"issue":"3","key":"9756_CR24","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/TIT.1956.1056798","volume":"2","author":"C.E. Shannon","year":"1956","unstructured":"Shannon, C.E.: The zero-error capacity of a noisy channel. IRE Trans. Inf. Theory 2(3), 8\u201319 (1956)","journal-title":"IRE Trans. Inf. Theory"},{"key":"9756_CR25","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1007\/BFb0030890","volume-title":"Computing and Combinatorics","author":"V.V. Vazirani","year":"1995","unstructured":"Vazirani, V.V.: Primal-dual schema based approximation algorithms (abstract). In: Computing and Combinatorics, pp. 650\u2013652 (1995)"},{"issue":"4","key":"9756_CR26","doi-asserted-by":"crossref","first-page":"1438","DOI":"10.1137\/040605461","volume":"27","author":"J. Eshof vanden","year":"2006","unstructured":"vanden Eshof, J., Hochbruck, M.: Preconditioning Lanczos approximations to the matrix exponential. SIAM J. Sci. Comput. 27(4), 1438\u20131457 (2006)","journal-title":"SIAM J. Sci. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9756-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9756-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9756-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T14:06:41Z","timestamp":1644329201000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9756-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,13]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9756"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9756-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,13]]}}}