{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:30Z","timestamp":1725665070449},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_1","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:22:21Z","timestamp":1330298541000},"page":"1-14","source":"Crossref","is-referenced-by-count":5,"title":["Polynomial time approximation schemes for some dense instances of NP-hard optimization problems"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/rsa.3240060409","volume":"6","author":"N. Alon","year":"1995","unstructured":"N. Alon, A. Frieze and D. Welsh, Polynomial Time Randomized Approximation Schemes for the Tutte Polynomial of Dense Graphs, Random Structures and Algorithms 6 (1995), pp. 459\u2013478.","journal-title":"Random Structures and Algorithms"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, A. Frieze and H. Kaplan, A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangements, Proc. 37th IEEE FOCS (1996), pp. 21\u201330.","DOI":"10.1109\/SFCS.1996.548460"},{"key":"1_CR3","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.","DOI":"10.1145\/225058.225140"},{"key":"1_CR4","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":"1_CR5","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.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"1_CR6","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"M. Bern and P. Plassmann, The Steiner Problem with Edge Lengths 1 and 2, Inform. Process. Lett. 32 (1989), pp. 171\u2013176.","journal-title":"Inform. Process. Lett."},{"key":"1_CR7","unstructured":"A.Z. Broder, How Hard is it to Marry at Random (On the Approximation of the Permanent), Proc. 18th ACM STOC (1986), pp. 50\u201358, Erratum in Proc. 20th ACM STOC (1988), p. 551."},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"P. Chinn","year":"1982","unstructured":"P. Chinn, J. Chvatalova, A. Dewdney, N. Gibbs, The Bandwidth Problem for Graphs and Matrices \u2014 A Survey, Journal of Graph Theory 6 (1982), pp. 223\u2013254.","journal-title":"Journal of Graph Theory"},{"key":"1_CR9","unstructured":"A. Clementi and L. Trevisan, Improved Nonapproximability Result for Vertex Cover with Density Constraints, Proc. 2nd Int. Conference, COCOON '96, Springer-Verlag (1996), pp. 333\u2013342."},{"key":"1_CR10","volume-title":"Technical Report LSI-94-16-R","author":"J. Diaz","year":"1994","unstructured":"J. Diaz, M. Serna and P. Spirakis, Some Remarks on the Approximability of Graph Layout Problems, Technical Report LSI-94-16-R, Univ. Politec, Catalunya (1994)."},{"key":"1_CR11","unstructured":"M.E. Dyer, A. Frieze and M.R. Jerrum, Approximately Counting Hamilton Cycles in Dense Graphs, Proc. 4th ACM-SIAM SODA (1994), pp. 336\u2013343."},{"key":"1_CR12","unstructured":"U. Feige, A Threshold of In n for Approximating Set Cover, Proc. 28th ACM STOC (1996), pp. 314\u2013318."},{"key":"1_CR13","doi-asserted-by":"crossref","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":"W. Fernandez-de-la-Vega, MAX-CUT has a Randomized Approximation Scheme in Dense Graphs, Random Structures and Algorithms 8 (1996), pp. 187\u2013999.","journal-title":"Random Structures and Algorithms"},{"key":"1_CR14","unstructured":"W. Fernandez-de-la-Vega and M. Karpinski, Polynomial Time Approximability of Dense Weighted Instances of MAX-CUT, Research Report No. 85171-CS, University of Bonn (1997)."},{"key":"1_CR15","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez-de-la-Vega","year":"1981","unstructured":"W. Fernandez-de-la-Vega, G. S. Lueker, Bin Packing Can be Solved Within 1+\u2208 in Linear Time, Combinatorica 1 (1981), pp. 349\u2013355.","journal-title":"Combinatorica"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"A. Frieze and R. Kannan, The Regularity Lemma and Approximation Schemes for Dense Problems, Proc. 37th IEEE FOCS (1996), pp. 12\u201320.","DOI":"10.1109\/SFCS.1996.548459"},{"key":"1_CR17","unstructured":"A. Frieze and R. Kannan, Quick Approximation to Matrices and Applications, Manuscript (1997)."},{"key":"1_CR18","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. Garey","year":"1978","unstructured":"M. Garey, R. Graham, D. Johnson, D. Knuth, Complexity Results For Bandwidth Minimization, SIAM J. Appl. Math. 34 (1978), pp. 477\u2013495.","journal-title":"SIAM J. Appl. Math."},{"key":"1_CR19","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979)."},{"key":"1_CR20","unstructured":"M. Goemans and D. Williamson, 878-approximation Algorithms for MAX-CUT and MAX2SAT, Proc. 26th ACM STOC (1994), pp. 422\u2013431."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser and D. Ron, Property Testing and its Connection to Learning and Approximation, Proc. 37th IEEE FOCS (1996), pp. 339\u2013348.","DOI":"10.1109\/SFCS.1996.548493"},{"key":"1_CR22","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02090396","volume":"24","author":"J. Haralambides","year":"1991","unstructured":"J. Haralambides, F. Makedon, B. Monien, Bandwidth Minimization: An Approximation Algorithm for Caterpillars, Math. Systems Theory 24 (1991), pp. 169\u2013177.","journal-title":"Math. Systems Theory"},{"key":"1_CR23","unstructured":"J. H\u00e5stad, Clique is Hard to Approximate within n\n1\u2212\u2208\n, Proc. 37th IEEE FOCS (1986), pp. 627\u2013636."},{"key":"1_CR24","unstructured":"D. Hochbaum, Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems, in Approximation Algorithms for NP-hard Problems (D. Hochbaum, ed.), PWS Publ. Co. (1997), pp. 94\u2013143."},{"key":"1_CR25","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. H. Ibarra","year":"1975","unstructured":"O. H. Ibarra, C. E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subsets Problems, J. ACM 22 (1975), pp. 463\u2013468.","journal-title":"J. ACM"},{"key":"1_CR26","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M. R. Jerrum","year":"1989","unstructured":"M. R. Jerrum and A. Sinclair, Approximating the Permanent, SIAM J. Comput. 18 (1989), pp. 1149\u20131178.","journal-title":"SIAM J. Comput."},{"key":"1_CR27","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, Approximation Algorithms for Combinatorial Problems, J. Comput. System Sciences 9 (1974), pp. 256\u2013278.","journal-title":"J. Comput. System Sciences"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"N. Karmarkar and R. M. Karp, An Efficient Approximation Scheme for the One-dimensional Bin-Packing Problem, Proc. 23rd IEEE FOCS (1982), pp. 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"1_CR29","unstructured":"R.M. Karp, Reducibility among Combinatorial Problems, in Complexity of Computer Computations (R. Miller and J. Thatcher, ed.), Plenum Press (1972), pp. 85\u2013103."},{"key":"1_CR30","unstructured":"M. Karpinski, J. Wirtgen and A. Zelikovsky, An Approximation Algorithm for the Bandwidth Problem on Dense Graphs, ECCC Technical Report TR 97-017 (1997)."},{"key":"1_CR31","volume-title":"Technical Report TR-96-059","author":"M. Karpinski","year":"1996","unstructured":"M. Karpinski and A. Zelikovsky, Approximating Dense Cases of Covering Problems (Preliminary Version), Technical Report TR-96-059, International Computer Science Institute, Berkeley (1996)."},{"key":"1_CR32","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M. Karpinski","year":"1997","unstructured":"M. Karpinski and A. Zelikovsky, New Approximation Algorithms for the Steiner Tree Problem, J. of Combinatorial Optimization 1 (1997), pp. 47\u201365.","journal-title":"J. of Combinatorial Optimization"},{"key":"1_CR33","unstructured":"M. Karpinski and A. Zelikovsky, Approximating Dense Cases of Covering Problems, ECCC Technical Report TR 97-004, 1997, to appear in Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location, Princeton (1997)."},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"G. Kortsarz and D. Peleg, On Choosing a Dense Subgraph, Proc. 34th IEEE FOCS (1993), pp. 692\u2013701.","DOI":"10.1109\/SFCS.1993.366818"},{"key":"1_CR35","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0607057","volume":"7","author":"B. Monien","year":"1986","unstructured":"B. Monien, The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete. SIAM J. Alg. Disc. Math. 7 (1986), pp. 505\u2013514.","journal-title":"SIAM J. Alg. Disc. Math."},{"key":"1_CR36","unstructured":"C. Papadimitriou, Computational Complexity, Addison-Wesley, (1994)."},{"key":"1_CR37","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, Optmization, Approximation and Complexity Classes, J. Comput. System Sciences 43 (1991), pp. 425\u2013440.","journal-title":"J. Comput. System Sciences"},{"key":"1_CR38","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1006\/jcss.1996.0058","volume":"53","author":"C. Papadimitriou","year":"1996","unstructured":"C. Papadimitriou and M. Yannakakis, On Limited Nondeterminism and the Complexity of the VC-dimension, J. Comput. System Sciences 53 (1996), pp. 161\u2013170.","journal-title":"J. Comput. System Sciences"},{"key":"1_CR39","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan, Probabilistic Construction of Deterministic Algorithms: Approximate Packing Integer Programs, J. Comput. System Sciences 37 (1988), pp. 130\u2013143.","journal-title":"J. Comput. System Sciences"},{"key":"1_CR40","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0012-365X(93)E0219-T","volume":"142","author":"L. Smithline","year":"1995","unstructured":"L. Smithline, Bandwidth of the Complete k-ary Tree, Discrete Mathematics 142 (1995), pp. 203\u2013212.","journal-title":"Discrete Mathematics"},{"key":"1_CR41","unstructured":"M. Yannakakis, On the Approximation of Maximum Satisfiability, Proc. 3rd ACM-SIAM SODA (1992), pp. 1\u20139."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:43:19Z","timestamp":1619574199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}