{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:46:25Z","timestamp":1725558385485},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642137303"},{"type":"electronic","value":"9783642137310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_15","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T11:00:50Z","timestamp":1276167650000},"page":"150-162","source":"Crossref","is-referenced-by-count":5,"title":["Feasible and Accurate Algorithms for Covering Semidefinite Programs"],"prefix":"10.1007","author":[{"given":"Garud","family":"Iyengar","sequence":"first","affiliation":[]},{"given":"David J.","family":"Phillips","sequence":"additional","affiliation":[]},{"given":"Cliff","family":"Stein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Hazan, E., Kale, S.: Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In: Proceedings of the 46th Annual Symposium on Foundations of Computer Science (2005)","DOI":"10.1109\/SFCS.2005.35"},{"key":"15_CR2","doi-asserted-by":"crossref","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 (2007)","DOI":"10.1145\/1250790.1250823"},{"key":"15_CR3","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.\u00a0222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"15_CR4","unstructured":"Bienstock, D.: Potential function methods for approximately solving linear programming problems: theory and practice, Boston, MA. International Series in Operations Research & Management Science, vol.\u00a053 (2002)"},{"key":"15_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"},{"key":"15_CR6","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)"},{"key":"15_CR7","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"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/3-540-69346-7_26","volume-title":"Integer Programming and Combinatorial Optimization","author":"A.V. Goldberg","year":"1998","unstructured":"Goldberg, A.V., Oldham, J.D., Plotkin, S.A., Stein, C.: An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, pp. 338\u2013352. Springer, Heidelberg (1998)"},{"key":"#cr-split#-15_CR9.1","doi-asserted-by":"crossref","unstructured":"Iyengar, G., Phillips, D.J., Stein, C.: Approximation algorithms for semidefinite packing problems with applications to maxcut and graph coloring. In: Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization, pp. 152???166 (2005);","DOI":"10.1007\/11496915_12"},{"key":"#cr-split#-15_CR9.2","unstructured":"Submitted to SIAM Journal on Optimization"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Iyengar, G., Phillips, D.J., Stein, C.: Feasible and accurate algorithms for covering semidefinite programs. Tech. rep., Optimization online (2010)","DOI":"10.1007\/978-3-642-13731-0_15"},{"key":"15_CR11","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":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/3-540-48777-8_24","volume-title":"Integer Programming and Combinatorial Optimization","author":"P. Klein","year":"1999","unstructured":"Klein, P., Young, N.: On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 320\u2013327. Springer, Heidelberg (1999)"},{"key":"15_CR13","unstructured":"Lu, Z., Monteiro, R., Yuan, M.: Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression, Arxiv preprint arXiv:0904.0691 (2009)"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y. Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of nonsmooth functions. Mathematical Programming\u00a0103, 127\u2013152 (2005)","journal-title":"Mathematical Programming"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10107-006-0001-8","volume":"110","author":"Y. Nesterov","year":"2007","unstructured":"Nesterov, Y.: Smoothing technique and its applications in semidefinite optimization. Mathematical Programming\u00a0110, 245\u2013259 (2007)","journal-title":"Mathematical Programming"},{"key":"15_CR16","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":"15_CR17","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":"15_CR18","doi-asserted-by":"publisher","first-page":"2239","DOI":"10.1109\/TSP.2006.872578","volume":"54","author":"N. Sidiropoulos","year":"2006","unstructured":"Sidiropoulos, N., Davidson, T., Luo, Z.: Transmit beamforming for physical-layer multicasting. IEEE Transactions on Signal Processing\u00a054, 2239 (2006)","journal-title":"IEEE Transactions on Signal Processing"},{"key":"15_CR19","first-page":"207","volume":"10","author":"K. Weinberger","year":"2009","unstructured":"Weinberger, K., Saul, L.: Distance metric learning for large margin nearest neighbor classification. The Journal of Machine Learning Research\u00a010, 207\u2013244 (2009)","journal-title":"The Journal of Machine Learning Research"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:42:19Z","timestamp":1606185739000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}