{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:08:29Z","timestamp":1725548909489},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_5","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"57-68","source":"Crossref","is-referenced-by-count":4,"title":["Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms"],"prefix":"10.1007","author":[{"given":"Petros","family":"Drineas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael W.","family":"Mahoney","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., de la Vega, W.F., Kannan, R., Karpinski, M.: Random sampling and approximation of MAX-CSP problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 232\u2013239 (2002)","DOI":"10.1145\/509907.509945"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/S0022-0000(03)00008-4","volume":"67","author":"N. Alon","year":"2003","unstructured":"Alon, N., de la Vega, W.F., Kannan, R., Karpinski, M.: Random sampling and approximation of MAX-CSPs. Journal of Computer and System Sciences\u00a067, 212\u2013243 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 284\u2013293 (1995)","DOI":"10.1145\/225058.225140"},{"key":"5_CR4","unstructured":"Bar-Yossef, Z.: The Complexity of Massive Data Set Computations. PhD thesis, University of California, Berkeley (2002)"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z.: Sampling lower bounds via information theory. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 335\u2013344 (2003)","DOI":"10.1145\/780542.780593"},{"issue":"3","key":"5_CR6","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U","volume":"8","author":"W.F. Vega de la","year":"1996","unstructured":"de la Vega, W.F.: MAX-CUT has a randomized approximation scheme in dense graphs. Random Structures and Algorithms\u00a08(3), 187\u2013198 (1996)","journal-title":"Random Structures and Algorithms"},{"key":"5_CR7","unstructured":"de la Vega, W.F., Karpinski, M.: A polynomial time approximation scheme for subdense MAX-CUT. Technical Report TR02-044, Electronic Colloquium on Computational Complexity (2002)"},{"key":"5_CR8","unstructured":"Drineas, P., Frieze, A., Kannan, R., Vempala, S., Vinay, V.: Clustering in large graphs and matrices. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 291\u2013299 (1999)"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Drineas, P., Kannan, R.: Fast Monte-Carlo algorithms for approximate matrix multiplication. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 452\u2013459 (2001)","DOI":"10.1109\/SFCS.2001.959921"},{"key":"5_CR10","unstructured":"Drineas, P., Kannan, R.: Pass efficient algorithms for approximating large matrices. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 223\u2013232 (2003)"},{"key":"5_CR11","unstructured":"Drineas, P., Kannan, R., Mahoney, M.W.: Sampling sub-problems of heterogeneous MAX-2-CSP problems and approximation algorithms (manuscript)"},{"key":"5_CR12","unstructured":"Drineas, P., Kannan, R., Mahoney, M.W.: Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. Technical Report YALEU\/DCS\/TR-1269, Yale University Department of Computer Science, New Haven, CT (February 2004)"},{"key":"5_CR13","unstructured":"Drineas, P., Kannan, R., Mahoney, M.W.: Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix. Technical Report YALEU\/DCS\/TR-1270, Yale University Department of Computer Science, New Haven, CT (February 2004)"},{"key":"5_CR14","unstructured":"Drineas, P., Kannan, R., Mahoney, M.W.: Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition. Technical Report YALEU\/DCS\/TR-1271, Yale University Department of Computer Science, New Haven, CT (February 2004)"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Drineas, P., Kannan, R., Mahoney, M.W.: Sampling sub-problems of heterogeneous Max-Cut problems and approximation algorithms. Technical Report YALEU\/DCS\/TR-1283, Yale University Department of Computer Science, New Haven, CT (April 2004)","DOI":"10.1007\/978-3-540-31856-9_5"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Frieze, A., Kannan, R.: The regularity lemma and approximation schemes for dense problems. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pp. 12\u201320 (1996)","DOI":"10.1109\/SFCS.1996.548459"},{"issue":"2","key":"5_CR17","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A. Frieze","year":"1999","unstructured":"Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica\u00a019(2), 175\u2013220 (1999)","journal-title":"Combinatorica"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pp. 339\u2013348 (1996)","DOI":"10.1109\/SFCS.1996.548493"},{"key":"5_CR19","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1989","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins University Press, Baltimore (1989)"},{"key":"5_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"R.A. Horn","year":"1985","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New York (1985)"},{"key":"5_CR21","volume-title":"Monte Carlo Strategies in Scientific Computing","author":"J.S. Liu","year":"2001","unstructured":"Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, New York (2001)"},{"issue":"2","key":"5_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"M.E.J. Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Review\u00a045(2), 167\u2013256 (2003)","journal-title":"SIAM Review"},{"key":"5_CR23","volume-title":"Matrix Perturbation Theory","author":"G.W. Stewart","year":"1990","unstructured":"Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Academic Press, New York (1990)"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:29:52Z","timestamp":1605760192000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}