{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T23:28:32Z","timestamp":1660692512716},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,4]]},"abstract":"\n This work addresses\n k-restriction problems<\/jats:italic>\n , which unify combinatorial problems of the following type: The goal is to construct a short list of strings in \u03a3\n \n m<\/jats:italic>\n <\/jats:sup>\n that satisfies a given set of\n k<\/jats:italic>\n -wise demands. For every\n k<\/jats:italic>\n positions and every demand, there must be at least one string in the list that satisfies the demand at these positions. Problems of this form frequently arise in different fields in Computer Science.The standard approach for deterministically solving such problems is via almost\n k<\/jats:italic>\n -wise independence or\n k<\/jats:italic>\n -wise approximations for other distributions. We offer a generic algorithmic method that yields considerably smaller constructions. To this end, we generalize a previous work of Naor et al. [1995]. Among other results, we enhance the combinatorial objects in the heart of their method, called splitters, and construct\n multi-way splitters<\/jats:italic>\n , using a new discrete version of the topological\n Necklace Splitting Theorem<\/jats:italic>\n [Alon 1987].We utilize our methods to show improved constructions for\n group testing<\/jats:italic>\n [Ngo and Du 2000] and\n generalized hashing<\/jats:italic>\n [Alon et al. 2003], and an improved inapproximability result for SET-COVER under the assumption\n P<\/jats:italic>\n \u2260\n NP<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/1150334.1150336","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"153-177","source":"Crossref","is-referenced-by-count":179,"title":["Algorithmic construction of sets for\n *k<\/i>\n -restrictions"],"prefix":"10.1145","volume":"2","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}]},{"given":"Dana","family":"Moshkovitz","sequence":"additional","affiliation":[{"name":"The Weizmann Institute, Rehovot, Israel"}]},{"given":"Shmuel","family":"Safra","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0001-8708(87)90055-7","article-title":"Splitting necklaces","volume":"63","author":"Alon N.","year":"1987","journal-title":"Adv. Math."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/18.119713","article-title":"Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs","volume":"38","author":"Alon N.","year":"1992","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2003.08.001"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 31st IEEE Symposium on Foundations of Computer Science.","volume":"2","author":"Alon N."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing. ACM","author":"Arora S."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 25th ACM Symposium on Theory of Computing. ACM","author":"Bellare M."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 3rd ACM Symposium on Theory of Computing. ACM","author":"Cook S. A.","year":"1971"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 31st ACM Symposium on Theory of Computing. ACM","author":"Dinur I."},{"key":"e_1_2_1_11_1","volume-title":"Series on Applied Mathematics","volume":"12","author":"Du D. Z."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199808)13:1%3C1::AID-RSA1%3E3.0.CO;2-W"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 25th ACM Symposium on Theory of Computing, ACM","author":"Koller D."},{"key":"e_1_2_1_15_1","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 L.","year":"1975","journal-title":"Disc. Math."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 36th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Naor M."},{"key":"e_1_2_1_19_1","volume-title":"DIMACS Series on Discrete Mathematics Theoretical Compuer Science","volume":"55","author":"Ngo H. Q."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing. ACM","author":"Raz R."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 28th ACM Symposium on Theory of Computing. ACM","author":"Slavik P.","year":"1996"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314240"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"van Leeuwen J. 1990. Graph Algorithms Handbook of Theoretical Computer Science (J. Van Leeuwen Ed.). Vol. A (Algorithms and Complexity). Chap. 10 MIT Press Cambridge MA 525--631. van Leeuwen J. 1990. Graph Algorithms Handbook of Theoretical Computer Science (J. Van Leeuwen Ed.). Vol. A (Algorithms and Complexity). Chap. 10 MIT Press Cambridge MA 525--631.","DOI":"10.1016\/B978-0-444-88071-0.50015-1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1150334.1150336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T09:11:30Z","timestamp":1613812290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1150334.1150336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1145\/1150334.1150336"],"URL":"http:\/\/dx.doi.org\/10.1145\/1150334.1150336","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2006,4]]}}}*