{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T08:02:29Z","timestamp":1773043349458,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662447765","type":"print"},{"value":"9783662447772","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44777-2_20","type":"book-chapter","created":{"date-parts":[[2014,8,16]],"date-time":"2014-08-16T06:43:15Z","timestamp":1408171395000},"page":"235-246","source":"Crossref","is-referenced-by-count":15,"title":["Nearly Tight Approximability Results for Minimum Biclique Cover and Partition"],"prefix":"10.1007","author":[{"given":"Parinya","family":"Chalermsook","sequence":"first","affiliation":[]},{"given":"Sandy","family":"Heydrich","sequence":"additional","affiliation":[]},{"given":"Eugenia","family":"Holm","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Karrenbauer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"20_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1137\/080729256","volume":"40","author":"C. Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput.\u00a040(2), 567\u2013596 (2011)","journal-title":"SIAM J. Comput."},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45526-4_1","volume-title":"Automata Implementation","author":"J. Amilhastre","year":"2001","unstructured":"Amilhastre, J., Janssen, P., Vilarem, M.-C.: FA minimisation heuristics for a class of finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol.\u00a02214, pp. 1\u201312. Springer, Heidelberg (2001)"},{"issue":"2-3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0166-218X(98)00039-0","volume":"86","author":"J. Amilhastre","year":"1998","unstructured":"Amilhastre, J., Vilarem, M., Janssen, P.: Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs. Discrete Applied Mathematics\u00a086(2-3), 125\u2013144 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more. In: Khanna, S. (ed.) SODA, pp. 1557\u20131576. SIAM (2013)","DOI":"10.1137\/1.9781611973105.112"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses. In: FOCS, pp. 370\u2013379. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.47"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/978-3-642-54423-1_36","volume-title":"LATIN 2014: Theoretical Informatics","author":"P. Chalermsook","year":"2014","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Coloring graph powers: Graph product bounds and hardness of approximation. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol.\u00a08392, pp. 409\u2013420. Springer, Heidelberg (2014)"},{"key":"20_CR8","first-page":"1","volume-title":"SACMAT 2008","author":"A. Ene","year":"2008","unstructured":"Ene, A., Horne, W., Milosavljevic, N., Rao, P., Schreiber, R., Tarjan, R.E.: Fast exact and heuristic methods for role minimization problems. In: SACMAT 2008, pp. 1\u201310. ACM, New York (2008)"},{"issue":"4","key":"20_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00453-006-0159-8","volume":"47","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. Algorithmica\u00a047(4), 439\u2013452 (2007)","journal-title":"Algorithmica"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Reif, J.H. (ed.) STOC, pp. 534\u2013543. ACM (2002)","DOI":"10.1145\/509984.509985"},{"issue":"2","key":"20_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U. Feige","year":"2004","unstructured":"Feige, U.: Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics\u00a018(2), 219\u2013225 (2004)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. Journal of Computer and System Sciences\u00a057, 187\u2013199 (1998)","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"20_CR13","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.jcss.2006.11.002","volume":"73","author":"G. Gramlich","year":"2007","unstructured":"Gramlich, G., Schnitger, G.: Minimizing NFA\u2019s and regular expressions. J. Comput. Syst. Sci.\u00a073(6), 908\u2013923 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"20_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0095-8956(91)90006-6","volume":"51","author":"D.A. Gregory","year":"1991","unstructured":"Gregory, D.A., Pullman, N.J., Jones, K.F., Lundgren, J.R.: Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices. J. Comb. Theory, Ser. B\u00a051(1), 73\u201389 (1991)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73208-2_21","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M.: Inapproximability of nondeterministic state and transition complexity assuming P \u2260 NP. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 205\u2013216. Springer, Heidelberg (2007)"},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Information Processing Letters\u00a045(1), 19\u201323 (1993)","journal-title":"Information Processing Letters"},{"issue":"3","key":"20_CR17","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M. Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata\u2013a survey. Information and Computation\u00a0209(3), 456\u2013470 (2011)","journal-title":"Information and Computation"},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/3-540-54233-7_169","volume-title":"ICALP","author":"T. Jiang","year":"1991","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. In: Albert, J.L., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 629\u2013640. Springer, Heidelberg (1991)"},{"issue":"3","key":"20_CR19","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences\u00a09(3), 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11786986_21","volume-title":"Automata, Languages and Programming","author":"S. Khot","year":"2006","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 226\u2013237. Springer, Heidelberg (2006)"},{"key":"20_CR21","unstructured":"Milind Dawande, P.K., Tayur, S.: On the biclique problem in bipartite graphs. GSIA Working Paper, Carnegie Mellon University, Pittsburgh (1996)"},{"issue":"1","key":"20_CR22","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00383169","volume":"7","author":"H. M\u00fcller","year":"1990","unstructured":"M\u00fcller, H.: Alternating cycle-free matchings. Order\u00a07(1), 11\u201321 (1990)","journal-title":"Order"},{"issue":"1-3","key":"20_CR23","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0012-365X(94)00350-R","volume":"149","author":"H. M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: On edge perfectness and classes of bipartite graphs. Discrete Mathematics\u00a0149(1-3), 159\u2013187 (1996)","journal-title":"Discrete Mathematics"},{"issue":"3-4","key":"20_CR24","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0025-5564(78)90088-3","volume":"40","author":"D.S. Nau","year":"1978","unstructured":"Nau, D.S., Markowsky, G., Woodbury, M.A., Amos, D.B.: A mathematical analysis of human leukocyte antigen serology. Mathematical Biosciences\u00a040(3-4), 243\u2013270 (1978)","journal-title":"Mathematical Biosciences"},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.ic.2011.03.008","volume":"213","author":"I. Nor","year":"2012","unstructured":"Nor, I., Hermelin, D., Charlat, S., Engelstadter, J., Reuter, M., Duron, O., Sagot, M.-F.: Mod\/Resc parsimony inference: Theory and application. Inf. Comput.\u00a0213, 23\u201332 (2012)","journal-title":"Inf. Comput."},{"issue":"5","key":"20_CR26","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"80","author":"J. Orlin","year":"1977","unstructured":"Orlin, J.: Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings)\u00a080(5), 406\u2013424 (1977)","journal-title":"Indagationes Mathematicae (Proceedings)"},{"issue":"3","key":"20_CR27","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(3), 651\u2013654 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"20_CR28","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"H. Simon","year":"1990","unstructured":"Simon, H.: On approximate solutions for combinatorial optimization problems. SIAM Journal on Discrete Mathematics\u00a03(2), 294\u2013310 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"20_CR29","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/1132516.1132612","volume-title":"Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006","author":"D. Zuckerman","year":"2006","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 681\u2013690. ACM, New York (2006)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44777-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T12:17:32Z","timestamp":1558959452000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44777-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447765","9783662447772"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44777-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}