{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T08:10:16Z","timestamp":1737360616227,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_4","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"24-34","source":"Crossref","is-referenced-by-count":9,"title":["Approximating Bounded Degree Instances of NP-Hard Problems"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern and Z. Sweedyk, The Hardness of Approximate Optima in Lattice, Codes, and Systems of Linear Equations, Proc. of 34th IEEE FOCS, 1993, 724\u2013733.","key":"4_CR1","DOI":"10.1109\/SFCS.1993.366815"},{"doi-asserted-by":"crossref","unstructured":"S. Arora, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems, Proc. 27th ACM STOC (1995), pp. 284\u2013293; the full version appeared in J. Comput. System Sciences 58 (1999), pp. 193\u2013210.","key":"4_CR2","DOI":"10.1006\/jcss.1998.1605"},{"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":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof Verification and Hardness of Approximation Problems, Proc. 33rd IEEE FOCS (1992), pp. 14\u201320.","key":"4_CR4","DOI":"10.1109\/SFCS.1992.267823"},{"unstructured":"P. Berman and M. F\u00fcrer, Approximating Maximum Independent Set in Bounded Degree Graphs, Proc. 5th ACM-SIAM SODA (1994), pp. 365\u2013371.","key":"4_CR5"},{"key":"4_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/3-540-60220-8_84","volume-title":"Proc. 4th Workshop on Algorithms and Data Structures","author":"P. Berman","year":"1995","unstructured":"P. Berman and T. Fujito, Approximating independent sets in degree 3 graphs, Proc. 4th Workshop on Algorithms and Data Structures, LNCS Vol. 955, Springer-Verlag, 1995, pp. 449\u2013460."},{"doi-asserted-by":"crossref","unstructured":"P. Berman, S. Hannenhalli and Karpinski, 1.375-Approximation Algorithm for Sorting by Reversals, Manuscript, 2001.","key":"4_CR7","DOI":"10.1007\/3-540-45749-6_21"},{"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."},{"unstructured":"P. Berman and M. Karpinski, Approximating Minimum Unsatisfiability of Linear Equations, ECCC Technical Report TR01-025 (2001).","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).","key":"4_CR10","DOI":"10.1007\/3-540-45465-9_53"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V. Bafna","year":"1996","unstructured":"V. Bafna and P. Pevzner, Genome Rearrangements and Sorting by Reversals, SIAM J. on Computing 25 (1996), pp. 272\u2013289.","journal-title":"SIAM J. on Computing"},{"doi-asserted-by":"crossref","unstructured":"A. Caprara Formulations and Hardness of Multiple Sorting by Reversals, Proc. ACM RECOMB\u201999, pp. 84\u201393.","key":"4_CR12","DOI":"10.1145\/299432.299461"},{"doi-asserted-by":"crossref","unstructured":"I. Dinur, G. Kindler and S. Safra, Approximating CVP to Within Almost Polynomial Factors is NP-hard, Proc. of 39th IEEE FOCS, 1998, 99\u2013109.","key":"4_CR13","DOI":"10.1109\/SFCS.1998.743433"},{"unstructured":"I. Dinur, G. Kindler, R. Raz and S. Safra, An Improved Lower Bound for Approximating CVP, 2000, submitted.","key":"4_CR14"},{"key":"4_CR15","series-title":"Lect Notes Comput Sci","first-page":"371","volume-title":"Proc. 16th STACS","author":"L. Engebretsen","year":"1999","unstructured":"L. Engebretsen, An Explicit Lower Bound for TSP with Distances One and Two, Proc. 16th STACS (1999), LNCS 1563 (1999), Springer, 1999, pp. 371\u2013382."},{"unstructured":"L. Engebretsen and M. Karpinski, Approximation Hardness of TSP with Bounded Metrics, ECCC Technical Report TR00-089 (2000), to appear in Proc. 28th ICALP (2001).","key":"4_CR16"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"U. Feige, A Threshold of ln n for Approximation Set Cover, J. of ACM 45 (1998), pp. 634\u2013652.","journal-title":"J. of ACM"},{"doi-asserted-by":"crossref","unstructured":"U. Feige and M. Goemans, Approximating the Value of Two Prover Proof Systems with Applications to MAX-2SAT and MAX-DICUT, Proc. 3rd Israel Symp. on Theory of Computing and Systems, 1995, pp. 182\u2013189.","key":"4_CR18","DOI":"10.1109\/ISTCS.1995.377033"},{"doi-asserted-by":"crossref","unstructured":"U. Feige and R. Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, Proc. 41st IEEE FOCS (2000), pp. 105\u2013115.","key":"4_CR19","DOI":"10.1109\/SFCS.2000.892070"},{"unstructured":"U. Feige, M. Karpinski, and M. Langberg, Improved Approximation of MAX-CUT on Graphs of Bounded Degree, ECCC Technical Report TR00-021 (2000), submitted to J. of Algorithms.","key":"4_CR20"},{"unstructured":"U. Feige, M. Karpinski, and M. Langberg, A Note on Approximation MAX-BISECTION on Regular Graphs, ECCC Technical Report TR00043 (2000), to appear in Information Processing Letters.","key":"4_CR21"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0020-0190(99)00048-4","volume":"70","author":"W. F. Vega de la","year":"1999","unstructured":"W. Fernandez de la Vega and M. Karpinski, On Approximation Hardness of Dense TSP and Other Path Problems, Information Processing Letters 70 (1999), pp. 53\u201355.","journal-title":"Information Processing Letters"},{"unstructured":"M. Goemans and D. Williamson, .878-approximation Algorithms for MAX-CUT and MAX2SAT, Proc. 26th ACM STOC (1994), pp. 422\u2013431.","key":"4_CR23"},{"doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some Optimal Inapproximability Results, Proc. 29th ACM STOC (1997), pp. 1\u201310.","key":"4_CR24","DOI":"10.1145\/258533.258536"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(00)00032-6","volume":"74","author":"J. H\u00e5stad","year":"2000","unstructured":"J. H\u00e5stad, On Bounded Occurrence Constraint Satisfaction, Information Processing Letters 74 (2000), pp. 1\u20136.","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"E. Halperin and U. Zwick, Improved Approximation Algorithms for Maximum Graph Bisection Problems, Manuscript, 2000.","key":"4_CR26","DOI":"10.1007\/3-540-45535-3_17"},{"key":"4_CR27","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_CR28","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"},{"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_CR29"},{"unstructured":"M. Karpinski and A. Zelikovsky, Approximating Dense Cases of Covering Problems, ECCC Technical Report TR 97-004, 1997, also in Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location, Princeton, 1997, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 40 (1998), pp. 169\u2013178.","key":"4_CR30"},{"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, 282\u2013296.","key":"4_CR31","DOI":"10.1109\/CCC.1997.612323"},{"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, Optimization, Approximation and Complexity Classes, J. Comput. System Sciences 43 (1991), pp. 425\u2013440.","journal-title":"J. Comput. System Sciences"},{"key":"4_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis, The Traveling Salesman Problem with Distances One and Two, Math. of Oper. Res. 18 (1993), pp. 1\u201311.","journal-title":"Math. of Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"L. Trevisan, Non-approximability Results for Optimization Problems on Bounded Degree Instances, to appear in Proc. 33rd ACM STOC (2001).","key":"4_CR34","DOI":"10.1145\/380752.380839"},{"key":"4_CR35","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(92)90103-3","volume":"44","author":"S. Virhwanathan","year":"1992","unstructured":"S. Virhwanathan, An Approximation Algorithm for the Asymetric Travelling Salesman Problem with Distances One and Two, Information Processing Letters 44 (1992), pp. 297\u2013302.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T07:28:10Z","timestamp":1737358090000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}