{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:18Z","timestamp":1781078238479,"version":"3.54.1"},"reference-count":29,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1994,12,1]],"date-time":"1994-12-01T00:00:00Z","timestamp":786240000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6803,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1994,12]]},"DOI":"10.1016\/s0022-0000(05)80068-6","type":"journal-article","created":{"date-parts":[[2005,8,20]],"date-time":"2005-08-20T11:18:35Z","timestamp":1124536715000},"page":"454-477","source":"Crossref","is-referenced-by-count":45,"title":["Efficient NC algorithms for set cover with applications to learning and geometry"],"prefix":"10.1016","volume":"49","author":[{"given":"Bonnie","family":"Berger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Rompel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter W.","family":"Shor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(05)80068-6_bib1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","article-title":"Partitioning arrangements of lines I: An efficient deterministic algorithm","volume":"5","author":"Agarwal","year":"1990","journal-title":"Discrete Computat. Geom."},{"key":"10.1016\/S0022-0000(05)80068-6_bib2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","article-title":"A fast and simple randomized parallel algorithm for the maximal independent set problem","volume":"7","author":"Alon","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(05)80068-6_bib3","series-title":"Set intersection problems","author":"Anderson","year":"1985"},{"key":"10.1016\/S0022-0000(05)80068-6_bib4","series-title":"Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures","first-page":"298","article-title":"Parallel algorithms for arrangements","author":"Anderson","year":"1990"},{"key":"10.1016\/S0022-0000(05)80068-6_bib5","series-title":"Proceedings of the 21st Annual ACM Symposium on Theory of Computing","first-page":"479","article-title":"Compact distributed data structures for adaptive routing","author":"Awerbuch","year":"1989"},{"key":"10.1016\/S0022-0000(05)80068-6_bib6","series-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","first-page":"273","article-title":"Learnability and the Vapnik-Chervonenkis dimension","author":"Blumer","year":"1986"},{"key":"10.1016\/S0022-0000(05)80068-6_bib7","series-title":"Proceedings of the 29th Annual Symposium on Foundations of Computer Science","first-page":"539","article-title":"A deterministic view of random sampling and its use in geometry","author":"Chazelle","year":"1989"},{"issue":"No. 3","key":"10.1016\/S0022-0000(05)80068-6_bib8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set-covering problem","volume":"4","author":"Chvatal","year":"1979","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0022-0000(05)80068-6_bib9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","article-title":"New applications of random sampling in computational geometry","volume":"2","author":"Clarkson","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0022-0000(05)80068-6_bib10","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","article-title":"A randomized algorithm for closest-point queries","volume":"17","author":"Clarkson","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(05)80068-6_bib11","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","article-title":"Applications of random sampling in computational geometry, II","volume":"4","author":"Clarkson","year":"1989","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0022-0000(05)80068-6_bib12","series-title":"Proceedings of the 4th ACM Symposium on Computational Geometry","first-page":"44","article-title":"The complexity of many faces in arrangements of lines and of segments","author":"Edelsbrunner","year":"1988"},{"key":"10.1016\/S0022-0000(05)80068-6_bib13","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","article-title":"Constructing arrangements of lines and hyperplanes with applications","volume":"15","author":"Edelsbrunner","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(05)80068-6_bib14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","article-title":"Epsilon-nets and simplex range queries","volume":"2","author":"Haussler","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0022-0000(05)80068-6_bib15","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","author":"Johnson","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(05)80068-6_bib16","series-title":"Complexity of Computer Computations","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1975"},{"issue":"No. 4","key":"10.1016\/S0022-0000(05)80068-6_bib17","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","article-title":"A fast parallel algorithm for the maximal independent set problem","volume":"32","author":"Karp","year":"1985","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(05)80068-6_bib18","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","article-title":"On the ratio of optimal integral and fractional covers","volume":"13","author":"Lov\u00e1sz","year":"1975","journal-title":"Discrete Math."},{"issue":"No. 4","key":"10.1016\/S0022-0000(05)80068-6_bib19","first-page":"1036","article-title":"A simple parallel algorithm for the maximal independent set problem SIAM","volume":"15","author":"Luby","year":"1986","journal-title":"J. Comput."},{"key":"10.1016\/S0022-0000(05)80068-6_bib20","series-title":"Proceedings of the 29th Annual Symposium on Foundations of Computer Science","first-page":"162","article-title":"Removing randomness in parallel computation without a processor penalty","author":"Luby","year":"1988"},{"key":"10.1016\/S0022-0000(05)80068-6_bib21","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF02187804","article-title":"Construction on epsilon nets","volume":"5","author":"Matou\u0161ek","year":"1990","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0022-0000(05)80068-6_bib22","series-title":"Proceedings of the 5th ACM Symposium on Computational Geometry","first-page":"1","article-title":"Cutting hyperplane arrangements","author":"Matou\u0161ek","year":"1990"},{"key":"10.1016\/S0022-0000(05)80068-6_bib23","series-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science","first-page":"8","article-title":"The probabilistic method yields deterministic parallel algorithms","author":"Motwani","year":"1989"},{"key":"10.1016\/S0022-0000(05)80068-6_bib24","series-title":"Proceedings of the 16th International Conference on Parallel Processing","article-title":"Optimal randomized and parallel algorithms for computational geometry","author":"Reif","year":"1987"},{"key":"10.1016\/S0022-0000(05)80068-6_bib25","series-title":"Proceedings of the 21st Annual ACM Symposium on Theory of Computating","first-page":"394","article-title":"Polling: a new randomized sampling technique for computational geometry","author":"Reif","year":"1989"},{"key":"10.1016\/S0022-0000(05)80068-6_bib26","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","article-title":"On the density of families of sets","volume":"13","author":"Sauer","year":"1972","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/S0022-0000(05)80068-6_bib27","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik","year":"1971","journal-title":"Theory of Probab. Appl."},{"key":"10.1016\/S0022-0000(05)80068-6_bib28","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0890-5401(92)90047-J","article-title":"Learning in parallel","volume":"96","author":"Vitter","year":"1992","journal-title":"Inform. Comput."},{"key":"10.1016\/S0022-0000(05)80068-6_bib29","series-title":"Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures","first-page":"169","article-title":"Constructing arrangements optimally in parallel","author":"Goodrich","year":"1991"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800686?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800686?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T22:27:07Z","timestamp":1548196027000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000005800686"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["S0022000005800686"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(05)80068-6","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}