{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:43Z","timestamp":1759638883986},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540792277"},{"type":"electronic","value":"9783540792284"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_25","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"282-293","source":"Crossref","is-referenced-by-count":11,"title":["Inapproximability of Maximum Weighted Edge Biclique and Its Applications"],"prefix":"10.1007","author":[{"given":"Jinsong","family":"Tan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N. Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Machine Learning\u00a056, 89\u2013113 (2004)","journal-title":"Machine Learning"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Dor, A., Chor, B., Karp, R., Yakhini, Z.: Discovering local structure in gene expression data: The Order-Preserving Submatrix Problem. In: Proceedings of RECOMB 2002, pp. 49\u201357 (2002)","DOI":"10.1145\/565196.565203"},{"key":"25_CR3","unstructured":"Bu, S.: The summarization of hierarchical data with exceptions. Master Thesis, Department of Computer Science, University of British Columbia (2004), \n                    \n                      http:\/\/www.cs.ubc.ca\/grads\/resources\/thesis\/Nov04\/Shaofeng_Bu.pdf"},{"key":"25_CR4","unstructured":"Bu, S., Lakshmanan, L.V.S., Ng, R.T.: MDL Summarization with Holes. In: Proceedings of VLDB 2005, pp. 433\u2013444 (2005)"},{"key":"25_CR5","first-page":"93","volume-title":"Proceedings of ISMB 2000","author":"Y. Cheng","year":"2000","unstructured":"Cheng, Y., Church, G.: Biclustering of expression data. In: Proceedings of ISMB 2000, pp. 93\u2013103. AAAI Press, Menlo Park (2000)"},{"issue":"2","key":"25_CR6","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1006\/jagm.2001.1199","volume":"41","author":"M. Dawande","year":"2001","unstructured":"Dawande, M., Keskinocak, P., Swaminathan, J.M., Tayur, S.: On Bipartite and multipartite clique problems. Journal of Algorithms\u00a041(2), 388\u2013403 (2001)","journal-title":"Journal of Algorithms"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of STOC 2002, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"key":"25_CR8","unstructured":"Feige, U., Kogan, S.: Hardness of approximation of the Balanced Complete Bipartite Subgraph problem. Technical Report MCS 2004-2004, The Weizmann Institute of Science (2004)"},{"key":"25_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"25_CR10","unstructured":"Fontana, P., Guha, S., Tan, J.: Recursive MDL Summarization and Approximation Algorithms (preprint, 2007)"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n\n                           1\u2009\u2212\u2009\u03b5\n                           . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S.: Ruling out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. In: Proceedings of FOCS 2004, pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/TCBB.2004.2","volume":"1","author":"S.C. Madeira","year":"2004","unstructured":"Madeira, S.C., Oliveira, A.L.: Biclustering algorithms for biological data analysis: a survey. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a01, 24\u201345 (2004)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Mishra, N., Ron, D., Swaminathan, R.: On finding large conjunctive clusters. In: Proceedings of COLT 2003, pp. 448\u2013462 (2003)","DOI":"10.1007\/978-3-540-45167-9_33"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R. Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Applied Mathematics\u00a0131, 651\u2013654 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR16","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1287\/mnsc.44.12.S161","volume":"44","author":"J.M. Swaminathan","year":"1998","unstructured":"Swaminathan, J.M., Tayur, S.: Managing Broader Product Lines Through Delayed Differentiation Using Vanilla Boxes. Management Science\u00a044, 161\u2013172 (1998)","journal-title":"Management Science"},{"issue":"2","key":"25_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-0040-4","volume":"48","author":"J. Tan","year":"2007","unstructured":"Tan, J., Chua, K., Zhang, L., Zhu, S.: Complexity study on clustering problems in microarray data analysis. Algorithmica\u00a048(2), 203\u2013219 (2007)","journal-title":"Algorithmica"},{"issue":"1","key":"25_CR18","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1093\/bioinformatics\/18.suppl_1.S136","volume":"18","author":"A. Tanay","year":"2002","unstructured":"Tanay, A., Sharan, R., Shamir, R.: Discovering statistically significant biclusters in gene expression data. Bioinformatics\u00a018(1), 136\u2013144 (2002)","journal-title":"Bioinformatics"},{"key":"25_CR19","unstructured":"Zhang, L., Zhu, S.: A New Clustering Method for Microarray Data Analysis. In: Proceedings of CSB 2002, pp. 268\u2013275 (2002)"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. In: Proceedings of STOC 2006, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:14:15Z","timestamp":1619522055000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_25","relation":{},"subject":[]}}