{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:18:54Z","timestamp":1725455934835},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540610434"},{"type":"electronic","value":"9783540498759"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0027116","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T11:08:23Z","timestamp":1132398503000},"page":"7-24","source":"Crossref","is-referenced-by-count":1,"title":["Parallel approximation of optimization problems"],"prefix":"10.1007","author":[{"given":"D. P.","family":"Bovet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Clementi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Crescenzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, and A. Itai (1986), \u201cA fast and simple randomized parallel algorithm for the maximal independent set problem\u201d, J. Algorithms 7, 567\u2013583.","journal-title":"J. Algorithms"},{"unstructured":"R. Anderson, and E.W. Mayr (1984), \u201cA P-complete problem and approximation to it\u201d, Technical Report STAN-CS-84-1014, Department of Computer Science, Stanford University.","key":"2_CR2"},{"doi-asserted-by":"crossref","unstructured":"A. Andreev, A. Clementi, P. Crescenzi, E. Dahlhaus, S. De Agostino, and J.D.P. Rolim (1995), \u201cThe parallel complexity of approximating the high degree subgraph problem\u201d, Proc. 6th Annual International Symposium on Algorithms and Computation, to appear.","key":"2_CR3","DOI":"10.1007\/BFb0015416"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"B.S. Baker (1994), \u201cApproximation algorithms for NP-complete problems on planar graphs\u201d, J. ACM 41, 153\u2013180.","journal-title":"J. ACM"},{"unstructured":"B. Berger, and J. Rompel (1989), \u201cSimulating (logc n)-wise independence in NC\u201d, Proc. 30th FOCS, 2\u20137.","key":"2_CR5"},{"doi-asserted-by":"crossref","unstructured":"B. Berger, J. Rompel, and P.W. Shor (1989), \u201cEfficient NC algorithms for set cover with applications to learning and geometry\u201d, Proc. 30th FOCS, 54\u201359.","key":"2_CR6","DOI":"10.1109\/SFCS.1989.63455"},{"unstructured":"G. Bongiovanni, P. Crescenzi, and S. De Agostino (1990), \u201cDescriptive Complexity and Parallel Approximation of Optimization Problems\u201d, unpublished manuscript (these results also appeared in P. Crescenzi, Descriptive complexity, average measure, and parallel approximation algorithms, Ph.D. Thesis, Department of Computer and Systems Science, University of Rome \u201cLa Sapienza\u201d, 1991).","key":"2_CR7"},{"doi-asserted-by":"crossref","unstructured":"E. Cohen (1992), \u201cApproximate max flow on small depth networks\u201d, Proc. 33rd FOCS, 648\u2013658.","key":"2_CR8","DOI":"10.1109\/SFCS.1992.267786"},{"unstructured":"P. Crescenzi, and V. Kann (1995), \u201cA compendium of NP optimization problems\u201d, Technical Report SI\/RR \u2014 95\/01, Department of Computer Science, University of Rome \u201cLa Sapienza\u201d (available by anonymous ftp either at encore.dsi.uniromal.it as \/pub\/crescenzi\/compendium.ps.Z or at nada.kth.se as Theory\/Viggo-Kann\/compendium.ps.Z).","key":"2_CR9"},{"doi-asserted-by":"crossref","unstructured":"P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan (1995), \u201cStructure in approximation classes\u201d, Proc. 1st COCOON, to appear.","key":"2_CR10","DOI":"10.1007\/BFb0030875"},{"doi-asserted-by":"crossref","unstructured":"J. Diaz, M. J. Serna, and J. Toran (1993), \u201cParallel approximation schemes for problems on planar graphs\u201d, Proc. 1st ESA, 145\u2013154.","key":"2_CR11","DOI":"10.1007\/3-540-57273-2_51"},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/BF02759702","volume":"1","author":"P. Erdos","year":"1963","unstructured":"P. Erdos (1963), \u201cOn the structure of linear graphs\u201d, Israel Journal of Mathematics 1, 156\u2013160.","journal-title":"Israel Journal of Mathematics"},{"unstructured":"M.R. Garey, and D.S. Johnson (1979), Computers and intractability: a guide to the theory of NP-completeness. Freeman.","key":"2_CR13"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1137\/0221011","volume":"21","author":"A. Goldberg","year":"1992","unstructured":"A. Goldberg, S. Plotkin, D. Shmoys, and E. Tardos (1992), \u201cInterior point methods in parallel computation\u201d, SIAM J. Computing 21, 140\u2013150.","journal-title":"SIAM J. Computing"},{"doi-asserted-by":"crossref","unstructured":"R. Greenlaw, H.J. Hoover, and W.L. Ruzzo (1995), Limits to parallel computation: P-completeness theory, Oxford University Press.","key":"2_CR15","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/176979.176984","volume":"26","author":"T.J. Harris","year":"1994","unstructured":"T.J. Harris (1994), \u201cA survey of PRAM simulation techniques\u201d, ACM Computing Surveys, 26, 187\u2013206.","journal-title":"ACM Computing Surveys"},{"unstructured":"H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns (1993), \u201cEvery Problem in MAX SNP has a Parallel Approximation Algorithm\u201d, manuscript.","key":"2_CR17"},{"doi-asserted-by":"crossref","unstructured":"H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns (1994), \u201cApproximation schemes using L-reductions\u201d, 14th FSTTCS, 342\u2013353.","key":"2_CR18","DOI":"10.1007\/3-540-58715-2_136"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1214\/aop\/1176996762","volume":"2","author":"A. Joffe","year":"1974","unstructured":"A. Joffe (1974), \u201cOn a set of almost deterministic k-independent random variables\u201d, Ann. Probability 2, 161\u2013162.","journal-title":"Ann. Probability"},{"key":"2_CR20","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 (1974), \u201cApproximation algorithms for combinatorial problems\u201d, J. Comput. System Sci. 9, 256\u2013278.","journal-title":"J. Comput. System Sci."},{"doi-asserted-by":"crossref","unstructured":"R. Karp, and V. Ramachandran (1990), \u201cParallel algorithms for shared-memory machines\u201d, in Handbook of Theoretical Computer Science: Algorithms and Complexity, J. van Leeuwen (ed.), Elsevier, 869\u2013941.","key":"2_CR21","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. Karp","year":"1985","unstructured":"R. Karp, and A. Wigderson (1985), \u201cA fast parallel algorithm for the maximal independent set problem\u201d, J. of ACM, 32, 762\u2013773.","journal-title":"J. of ACM"},{"doi-asserted-by":"crossref","unstructured":"S. Khuller, U. Vishkin, and N. Young (1994), \u201cPrimal-dual parallel approximation technique applied to weighted set and vertex covers\u201d, J. of Algorithms, 280\u2013289.","key":"2_CR23","DOI":"10.1006\/jagm.1994.1036"},{"unstructured":"L.M. Kirousis, M.J. Serna, and P. Spirakis (1989), \u201cThe parallel complexity of the connected subgraph problem\u201d, Proc. 30th FOCS, 446\u2013456.","key":"2_CR24"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L. Kucera","year":"1982","unstructured":"L. Kucera (1982), \u201cParallel computation and conflicts in memory access\u201d, Information Processing Letters, 14, 93\u201396.","journal-title":"Information Processing Letters"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby (1986), \u201cA simple parallel algorithm for the maximal independent set Problem\u201d, SIAM J. Computing 15, 1036\u20131053.","journal-title":"SIAM J. Computing"},{"doi-asserted-by":"crossref","unstructured":"M. Luby (1988), \u201cRemoving randomness in parallel computation without a processor penalty\u201d, Proc. 29th FOCS, 162\u2013173.","key":"2_CR27","DOI":"10.1109\/SFCS.1988.21934"},{"doi-asserted-by":"crossref","unstructured":"M. Luby, and N. Nisan (1993), \u201cA parallel approximation algorithm for positive linear programming\u201d, Proc. 25th STOC, 448\u2013457.","key":"2_CR28","DOI":"10.1145\/167088.167211"},{"unstructured":"E.W. Mayr (1988), \u201cParallel approximation algorithms\u201d, Proc. Fifth Generation Computer Systems, 542\u2013551.","key":"2_CR29"},{"unstructured":"C.H. Papadimitriou, and K. Steiglitz (1982), Combinatorial optimization. Algorithms and complexity. Prentice-Hall.","key":"2_CR30"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"C.H. Papadimitriou, and M. Yannakakis (1991), \u201cOptimization, approximation, and complexity classes\u201d, J. Comput. System Sci. 43, 425\u2013440.","journal-title":"J. Comput. System Sci."},{"doi-asserted-by":"crossref","unstructured":"S. Rajagopalan, and V.V. Vazirani (1993), \u201cPrimal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs\u201d, Proc. 34th FOCS, 322\u2013331.","key":"2_CR32","DOI":"10.1109\/SFCS.1993.366855"},{"doi-asserted-by":"crossref","unstructured":"M. Serna, and P. Spirakis (1989), \u201cThe approximability of problems complete for P\u201d, Proc. International Symposium on Optimal Algorithms, 193\u2013204.","key":"2_CR33","DOI":"10.1007\/3-540-51859-2_16"}],"container-title":["Lecture Notes in Computer Science","Solving Combinatorial Optimization Problems in Parallel"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0027116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T02:24:00Z","timestamp":1626747840000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0027116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540610434","9783540498759"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/bfb0027116","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}