{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T04:49:50Z","timestamp":1768711790004,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1007\/bf02523683","type":"journal-article","created":{"date-parts":[[2006,11,7]],"date-time":"2006-11-07T23:50:25Z","timestamp":1162943425000},"page":"449-462","source":"Crossref","is-referenced-by-count":10,"title":["Improved parallel approximation of a class of integer programming problems"],"prefix":"10.1007","volume":"17","author":[{"given":"N.","family":"Alon","sequence":"first","affiliation":[]},{"given":"A.","family":"Srinivasan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02523683_CR1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF02122549","volume":"8","author":"R. Aharoni","year":"1988","unstructured":"R. Aharoni, P. Erd\u0151s, and N. Linial. Optima of dual integer linear programs.Combinatorica, 8:13\u201320, 1988.","journal-title":"Combinatorica"},{"key":"BF02523683_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/18.119713","volume":"38","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth. Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs.IEEE Transactions on Information Theory, 38:509\u2013516, 1992.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"BF02523683_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"N. Alon, O. Goldreich, J. H\u00e5stad, and R. Peralta. Simple constructions of almostk-wise independent random variables.Random Structures and Algorithms, 3(3):289\u2013303, 1992.","journal-title":"Random Structures and Algorithms"},{"key":"BF02523683_CR4","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"N. Alon and M. Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions.Algorithmica, 16:434\u2013449, 1996.","journal-title":"Algorithmica"},{"key":"BF02523683_CR5","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1145\/115234.115347","volume":"38","author":"B. Berger","year":"1991","unstructured":"B. Berger and J. Rompel. Simulating (log c n)-wise independence in NC.Journal of the Association for Computing Machinery, 38:1026\u20131046, 1991.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF02523683_CR6","doi-asserted-by":"crossref","unstructured":"S. Chari, P. Rohatgi, and A. Srinivasan. Improved algorithms via approximations of probability distributions.Proc. ACM Symposium on Theory of Computing, pages 584\u2013592, 1994.","DOI":"10.1145\/195058.195411"},{"key":"BF02523683_CR7","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.Annals of Mathematical Statistics, 23:493\u2013509, 1952.","journal-title":"Annals of Mathematical Statistics"},{"issue":"23","key":"BF02523683_CR8","doi-asserted-by":"crossref","first-page":"3382","DOI":"10.1103\/PhysRevLett.69.3382","volume":"69","author":"A. M. Ferrenberg","year":"1992","unstructured":"A. M. Ferrenberg, D. P. Landau, and Y. J. Wong. Monte Carlo simulations: hidden errors from \u201cgood\u201d random number generators.Physical Review Letters, 69(23):3382\u20133384, 1992.","journal-title":"Physical Review Letters"},{"key":"BF02523683_CR9","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"W. Hoeffding. Probability inequalities for sums of bounded random variables.American Statistical Association Journal, 58:13\u201330, 1963.","journal-title":"American Statistical Association Journal"},{"key":"BF02523683_CR10","unstructured":"T.-S. Hsu. Graph augmentation and related problems: theory and practice. Ph.D. thesis, Department of Computer Sciences, University of Texas at Austin, October 1993."},{"key":"BF02523683_CR11","unstructured":"T.-S. Hsu, V. Ramachandran, and N. Dean. Parallel implementation of algorithms for finding connected components. InDIMACS International Algorithm Implementation Challenge, pages 1\u201314, 1994."},{"issue":"3","key":"BF02523683_CR12","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1145\/174130.174132","volume":"40","author":"H. J. Karloff","year":"1993","unstructured":"H. J. Karloff and P. Raghavan. Randomized algorithms and pseudorandom numbers.Journal of the Association for Computing Machinery, 40(3):454\u2013476, 1993.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF02523683_CR13","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz. On the ratio of optimal integral and fractional covers.Discrete Mathematics, 13:383\u2013390, 1975.","journal-title":"Discrete Mathematics"},{"issue":"2","key":"BF02523683_CR14","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/0022-0000(93)90033-S","volume":"47","author":"M. Luby","year":"1993","unstructured":"M. Luby. Removing randomness in parallel computation without a processor penalty.Journal of Computer and System Sciences, 47(2):250\u2013286, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02523683_CR15","doi-asserted-by":"crossref","unstructured":"M. Luby and N. Nisan. A parallel approximation algorithm for positive linear programming.proc. ACM Symposium on Theory of Computing, pages 448\u2013457, 1993.","DOI":"10.1145\/167088.167211"},{"key":"BF02523683_CR16","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/S0022-0000(05)80069-8","volume":"49","author":"R. Motwani","year":"1994","unstructured":"R. Motwani, J. Naor, and M. Naor. The probabilistic method yields deterministic parallel algorithms.Journal of Computer and System Sciences, 49:478\u2013516, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"BF02523683_CR17","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"J. Naor and M. Naor. Small-bias probability spaces: efficient constructions and applications.SIAM Journal on Computing, 22(4):838\u2013856, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"BF02523683_CR18","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S. A. Plotkin","year":"1995","unstructured":"S. A. Plotkin, D. B. Shmoys, and \u00c9. Tardos. Fast approximation algorithms for fractional packing and covering problems.Mathematics of Operations Research, 20:257\u2013301, 1995.","journal-title":"Mathematics of Operations Research"},{"key":"BF02523683_CR19","unstructured":"P. Raghavan. Randomized Rounding and Discrete Ham-Sandwich Theorems: Provably Good Algorithms for Routing and Packing Problems. Ph.D. thesis, University of California at Berkeley, July 1986. Also available as Computer Science Department Report UCB\/CSD 87\/312."},{"key":"BF02523683_CR20","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: approximating packing integer programs.Journal of Computer and Systems Sciences, 37:130\u2013143, 1988.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"BF02523683_CR21","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs.Combinatorica, 7:365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"BF02523683_CR22","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"J. P. Schmidt","year":"1995","unstructured":"J. P. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence.SIAM Journal on Discrete Mathematics, 8:223\u2013250, 1995.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"BF02523683_CR23","unstructured":"A. Schrijver, P. Seymour, and P. Winkler. The ring loading problem. In preparation."},{"key":"BF02523683_CR24","doi-asserted-by":"crossref","unstructured":"A. Srinivasan. Improved approximations of packing and covering problems.Proc. ACM Symposium on Theory of Computing, pages 268\u2013276, 1995.","DOI":"10.1145\/225058.225138"},{"key":"BF02523683_CR25","unstructured":"A. Srinivasan. An extension of the Lov\u00e1sz local lemma, and its applications to integer programming.Proc. ACM\/SIAM Symposium on Discrete Alogrithms, pages 6\u201315, 1996."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523683.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523683\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:39:44Z","timestamp":1558283984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523683"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["BF02523683"],"URL":"https:\/\/doi.org\/10.1007\/bf02523683","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}