{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:57Z","timestamp":1759638357046,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407201"},{"type":"electronic","value":"9783540451679"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45167-9_33","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:10:53Z","timestamp":1279840253000},"page":"448-462","source":"Crossref","is-referenced-by-count":18,"title":["On Finding Large Conjunctive Clusters"],"prefix":"10.1007","author":[{"given":"Nina","family":"Mishra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ram","family":"Swaminathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Gehrke, J.E., Gunopulos, D., Raghavan, P.: Automatic subspace clustering of high dimensional data for data mining applications. In: Proceedings of SIGMOD, pp. 94\u2013105 (1998)","DOI":"10.1145\/276304.276314"},{"key":"33_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Imielinski, T., Swami, A.: Mining association rules between sets of items in large databases. In: Proceedings of SIGMOD, pp. 207\u2013216 (1993)","DOI":"10.1145\/170036.170072"},{"key":"33_CR3","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s004930070001","volume":"20","author":"N. Alon","year":"2000","unstructured":"Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs. Combinatorica\u00a020, 451\u2013476 (2000)","journal-title":"Combinatorica"},{"key":"33_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1006\/jcss.1998.1605","volume":"58","author":"S. Arora","year":"1999","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences\u00a058, 193\u2013210 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"Arya, Garg, Khandekar, Munagala, Pandit: Local search heuristic for k-median and facility location problems. In: Proceedings of STOC (2001)","DOI":"10.1145\/380752.380755"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. In: Proceedings of FOCS, pp. 938\u2013247 (2002)","DOI":"10.1109\/SFCS.2002.1181947"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 84\u201395 (2000)","DOI":"10.1007\/3-540-44436-X_10"},{"key":"33_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceedings of FOCS, pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"33_CR9","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. Fernandez de la Vega","year":"1996","unstructured":"Fernandez de la Vega, W.: MAX-CUT has a randomized approximation scheme in dense graphs. Random Structures and Algorithms\u00a08, 187\u2013198 (1996)","journal-title":"Random Structures and Algorithms"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"A.P. Dempster","year":"1977","unstructured":"Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the EM algorithm (with discussion). Journal of the Royal Statistical Society series B\u00a039, 1\u201338 (1977)","journal-title":"Journal of the Royal Statistical Society series B"},{"key":"33_CR11","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: Proceedings of STOC, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"key":"33_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U.: Average case complexity and approximation complexity. In: Proceedings of STOC (2002)","DOI":"10.1145\/509984.509985"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"Flake, G., Lawrence, S., Lee Giles, C.: Efficient identification of web communities. In: Proceedings of KDD, pp. 150\u2013160 (2000)","DOI":"10.1145\/347090.347121"},{"issue":"2","key":"33_CR14","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":"33_CR15","doi-asserted-by":"crossref","unstructured":"Gibson, D., Kleinberg, J., Raghavan, P.: Inferring web communities from link topology. In: Proceedings of the 9th ACM Conference on Hypertext, Structural Queries, pp. 225\u2013234 (1998)","DOI":"10.1145\/276627.276652"},{"key":"33_CR16","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. UC Berkeley Tech Report, CSD-84-171 (1984)"},{"issue":"4","key":"33_CR17","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"issue":"2-3","key":"33_CR18","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T.F. Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoretical Computer Science\u00a038(2-3), 293\u2013306 (1985)","journal-title":"Theoretical Computer Science"},{"key":"33_CR19","doi-asserted-by":"crossref","unstructured":"Gunopulos, D., Mannila, H., Khardon, R., Toivonen, H.: Data mining, hypergraph transversals, and machine learning (extended abstract). In: Proceedings of PODS, pp. 209\u2013216 (1997)","DOI":"10.1145\/263661.263684"},{"issue":"3","key":"33_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D. Hochbaum","year":"1986","unstructured":"Hochbaum, D., Shmoys, D.: A unified approach to approximate algorithms for bottleneck problems. Journal of the ACM\u00a033(3), 533\u2013550 (1986)","journal-title":"Journal of the ACM"},{"key":"33_CR21","doi-asserted-by":"crossref","unstructured":"Jain, N., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and k-median problems. In: Proceedings of FOCS, pp. 2\u201313 (1999)","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"33_CR22","doi-asserted-by":"crossref","unstructured":"Kannan, R., Vempala, S., Vetta, A.: On clusterings \u2014 good, bad and spectral. In: IEEE (ed.) Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 367\u2013377 (2000)","DOI":"10.1109\/SFCS.2000.892125"},{"issue":"11\u201316","key":"33_CR23","first-page":"1481","volume":"31","author":"R. Kumar","year":"1999","unstructured":"Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Trawling the Web for emerging cyber-communities. Computer Networks (Amsterdam, Netherlands: 1999)\u00a031(11\u201316), 1481\u20131493 (1999)","journal-title":"Computer Networks (Amsterdam, Netherlands: 1999)"},{"key":"33_CR24","unstructured":"Michalski, R.S.: Knowledge acquisition through conceptual clustering: A theoretical framework and an algorithm for partitioning data into conjunctive concepts. Technical Report 1026, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois (1980)"},{"key":"33_CR25","unstructured":"Mishra, N., Oblinger, D., Pitt, L.: Sublinear time approximate clustering. In: Proceedings of SODA, pp. 439\u2013447 (2001)"},{"key":"33_CR26","doi-asserted-by":"crossref","unstructured":"Mishra, N., Ron, D., Swaminathan, R.: Large conjunctive clusters and bicliques (2002) (available from the authors)","DOI":"10.1007\/978-3-540-45167-9_33"},{"key":"33_CR27","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y.: Polynomial time approximation schemes for geometric k-clustering. In: IEEE (ed.) 41st Annual Symposium on Foundations of Computer Science, pp. 349\u2013358 (2000)","DOI":"10.1109\/SFCS.2000.892123"},{"key":"33_CR28","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete (2000) (unpublished manuscript)"},{"key":"33_CR29","first-page":"371","volume":"2","author":"L. Pitt","year":"1987","unstructured":"Pitt, L., Reinke, R.E.: Criteria for polynomial-time (conceptual) clustering. Machine Learning\u00a02, 371 (1987)","journal-title":"Machine Learning"},{"issue":"3","key":"33_CR30","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"D. Peleg","year":"2001","unstructured":"Peleg, D., Feige, U., Kortsarz, G.: The dense-k-subgraph problem. Algorithmica\u00a029(3), 410\u2013421 (2001)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Learning Theory and Kernel Machines"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45167-9_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T07:36:19Z","timestamp":1740296179000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45167-9_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407201","9783540451679"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45167-9_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}