{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:09:27Z","timestamp":1761401367356,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440406"},{"type":"electronic","value":"9783540456872"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45687-2_4","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:57:47Z","timestamp":1192784267000},"page":"59-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Approximability of the Minimum Bisection Problem: An Algorithmic Challenge"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"#cr-split#-4_CR1.1","doi-asserted-by":"crossref","unstructured":"S. Arors, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems, Proc. 27th ACM STOC (1995), pp. 284-293","DOI":"10.1145\/225058.225140"},{"key":"#cr-split#-4_CR1.2","doi-asserted-by":"crossref","unstructured":"the full version appeared in J. Comput. System Sciences 58 (1999), pp. 193-210.","DOI":"10.1006\/jcss.1998.1605"},{"key":"4_CR2","unstructured":"S. Arora and C. Lund, Hardness of Approximations, in Approximation Algorithms for NP-Hard Problems (D. Hochbaum, ed.), PWS Publ. Co. (1997), pp. 399\u2013446."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Proceedings of the 24th IEEE Foundation of Computer Science, 1983, pp. 265\u2013273.","DOI":"10.1109\/SFCS.1983.7"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F. Barahona","year":"1982","unstructured":"F. Barahona, On the Computational Complexity of Ising Spin Glass Models, J. Phys. A. Math. Gen. 15 (1982) pp. 3241\u20133253.","journal-title":"J. Phys. A. Math. Gen."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"F. Barahona and A. R. Mahjoub, On the Cut Polytope, Mathematical Programming 36 (1986), pp. 157\u2013173.","journal-title":"Mathematical Programming"},{"key":"4_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-48321-7_6","volume-title":"Proc. Fundamentals of Computation Theory","author":"C. Bazgan","year":"1999","unstructured":"C. Bazgan and W. Fernandez de la Vega, A Polynomial Time Approximation Scheme for Dense MIN 2SAT, Proc. Fundamentals of Computation Theory, LNCS 1684, Springer, 1999, pp. 91\u201399"},{"key":"4_CR7","unstructured":"C. Bazgan, W. Fernandez de la Vega and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction, ECCC Technical Report, TR01-034, submitted to Random Structures and Algorithms."},{"key":"4_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Proc. 26th ICALP","author":"P. Berman","year":"1999","unstructured":"P. Berman and M. Karpinski, On Some Tighter Inapproximability Results, Proc. 26th ICALP (1999), LNCS 1644, Springer, 1999, pp. 200\u2013209."},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"P. Berman and M. Karpinski, Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION, ECCC Technical Report, TR01-026, 2001, to appear in Proc. 29th ICALP (2002).","DOI":"10.1007\/3-540-45465-9_53"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"A. E. F. Clementi and L. Trevisan, Improved Non-approximability Results for Vertex Cover with Density Constraints, Proc. of 2nd Conference on Computing and Combinatorics, COCOON\u201996, Springer, 1996, pp. 333\u2013342.","DOI":"10.1007\/3-540-61332-3_167"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"U. Feige, M. Karpinski and M. Langberg, A Note on Approximation MAXBISECTION on Regular Graphs, ECCC Technical Report TR00-043, 2000, also in Information Processing Letters 79 (2001), pp, 181\u2013188.","DOI":"10.1016\/S0020-0190(00)00189-7"},{"key":"4_CR12","unstructured":"U. Feige and R. Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, Proc. 41st IEEE FOCS (2000), pp. 105\u2013115."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"U. Feige, R. Krauthgamer and K. Nissim, Aproximating the Minimum Bisection Size, Proc. 32nd ACM STOC (2000), pp. 530\u2013536.","DOI":"10.1145\/335305.335370"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"W. Fernandez de la Vega and M. Karpinski, Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT, ECCC Technical Report TR98-064 (1998), final version Random Structures and Algorithms 8 (2000), pp. 314\u2013332.","DOI":"10.1002\/1098-2418(200007)16:4<314::AID-RSA2>3.0.CO;2-E"},{"key":"4_CR15","unstructured":"W. Fernandez de la Vega, M. Karpinski and C. Kenyon, Polynomial Time Approximation Scheme for Metric MIN-BISECTION, Manuscript, 2002."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"W. Fernandez de la Vega, M. Karpinski, C. Kenyon and Y. Rabani, Ploynomial Time Approximation Schemes for Metric Min-Sum Clustering, ECCC Tech. Report TR02-025, 2002.","DOI":"10.1145\/780542.780550"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"W. Fernandez de la Vega and C. Kenyon, A Randomized Approximation Scheme for Metric MAX-CUT, Proc. 39th IEEE FOCS (1998), pp. 468\u2013471, final version Journal of Computer and System Sciences 63 (2001), pp. 531\u2013534.","DOI":"10.1006\/jcss.2001.1772"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. Hadlock","year":"1975","unstructured":"F. Hadlock, Finding a Maximum Cut of a Planar Graph in Polynomial Time, SIAM Journal on Computing 4 (1975), pp. 221\u2013225.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"D. S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, PWS, 1997.","DOI":"10.1145\/261342.571216"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"P. Indyk, A Sublinear Time Approximtion Scheme for Clustering in Metric Spaces, Proc. 40th IEEE FOCS (1999), 154\u2013159.","DOI":"10.1109\/SFFCS.1999.814587"},{"key":"4_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/3-540-44693-1_32","volume-title":"Proc. 18th STACS","author":"K. Jansen","year":"2001","unstructured":"K. Jansen, M. Karpinski, A. Lingas, and E. Seidel, Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs, Proc. 18th STACS (2001), LNCS 2010, Springer, 2001, pp. 365\u2013375."},{"key":"4_CR22","unstructured":"M. Jerrum, Personal communication, 2000."},{"key":"4_CR23","unstructured":"M. Jerrum and G. B. Sorkin, Simulated Annealing for Graph Bisection, Proc. 34th IEEE FOCS (1993), pp. 94\u2013103"},{"key":"4_CR24","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/s00453-001-0012-z","volume":"30","author":"M. Karpinski","year":"2001","unstructured":"M. Karpinski, Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems, Algorithmica 30 (2001), pp. 386\u2013397.","journal-title":"Algorithmica"},{"key":"4_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-44669-9_4","volume-title":"Proc. 13th Symp. on Fundamentals of Computation Theory","author":"M. Karpinski","year":"2001","unstructured":"M. Karpinski, Approximating bounded degree instances of NP-hard problems, Proc. 13th Symp. on Fundamentals of Computation Theory, LNCS 2138, Springer, 2001, pp. 24\u201334"},{"key":"4_CR26","unstructured":"M. Karpinski, M. Kowaluk, and A. Lingas, Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs, ECCC Technical Report TR00-051 (2000)."},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"M. Karpinski and A. Zelikovsky, Approximationg Dense Cases of Covering Problems, ECCC Technical Report TR 97-004, 1997, appeared also in DI-MACS Series in Discrete Mathematics and Theoretical Computer Science, Vol.40, 1998, pp. 169\u2013178.","DOI":"10.1090\/dimacs\/040\/11"},{"key":"4_CR28","doi-asserted-by":"crossref","unstructured":"S. Khanna, M. Sudan and L. Trevisan, Constraint Satisfaction: the approximability of minimization problems, Proc. of 12th IEEE Computational Complexity, 1997, pp. 282\u2013296.","DOI":"10.1109\/CCC.1997.612323"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1137\/S0895480191220836","volume":"7","author":"R. Kohli","year":"1994","unstructured":"R. Kohli, R. Krishnamurti and P. Mirchandani, The Minimum Satisfiability Problem, SIAM Journal on Discrete Mathematics 7 (1994), pp. 275\u2013283.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs, SIAM Journal of Applied Mathematics, 36 (1979), pp. 177\u2013189.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"M. Mezard, G. Parisi and M. A. Virasoro, Spin Glass Theory and Beyond, World Scientific, 1987.","DOI":"10.1142\/0271"},{"key":"4_CR32","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, Approximation and Complexity Classes, J. Comput. System Sciences 43 (1991), pp. 425\u2013440.","journal-title":"J. Comput. System Sciences"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2002"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45687-2_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T19:12:41Z","timestamp":1737486761000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45687-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440406","9783540456872"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-45687-2_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"4 October 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}