Algorithmic construction of sets for k-restrictions

ABSTRACT

This work addresses k-restriction problems, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σ^m that satisfies a given set of k-wise demands. For every k 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 k-wise independence or k-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 multi-way splitters, using a new discrete version of the topological Necklace Splitting Theorem [Alon 1987].We utilize our methods to show improved constructions for group testing [Ngo and Du 2000] and generalized hashing [Alon et al. 2003], and an improved inapproximability result for SET-COVER under the assumption P &neq; NP.

REFERENCES

• 1: Alon, N. 1987. Splitting necklaces. Adv. Math. 63, 3, 247--253.
• 2: Alon, N., Bruck, J., Naor, J., Naor, M., and Roth, R. 1992. Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inf. Theory 38, 509--516.
• 3: Noga Alon , Gérard Cohen , Michael Krivelevich , Simon Litsyn, Generalized hashing and parent-identifying codes, Journal of Combinatorial Theory Series A, v.104 n.1, p.207-215, October 2003 [doi>10.1016/j.jcta.2003.08.001]
• 4: Alon, N., Goldreich, O., Håastad, J., and Peralta, R. 1990. Simple constructions of almost k-wise independent random variables. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. Vol. 2. IEEE Computer Society Press, Los Alamitos, CA, 544--553.
• 5: Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
• 6: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 7: Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258642]
• 8: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 9: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 10: Irit Dinur , Eldar Fischer , Guy Kindler , Ran Raz , Shmuel Safra, PCP characterizations of NP: towards a polynomially-small error-probability, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.29-40, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301265]
• 11: Du, D. Z., and Hwang, F. K. 2000. Combinatorial Group Testing and its Applications, second ed. Series on Applied Mathematics, vol. 12. World Scientific, New York.
• 12: Guy Even , Oded Goldreich , Michael Luby , Noam Nisan , Boban Veličković, Efficient approximation of product distributions, Random Structures & Algorithms, v.13 n.1, p.1-16, Aug. 1998 [doi>10.1002/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W ]
• 13: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 14: Daphne Koller , Nimrod Megiddo, Constructing small sample spaces satisfying given constraints, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.268-277, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167168]
• 15: Lovász, L. 1975. On the ratio of optimal integral and fractional covers. Disc. Math. 13, 383--390.
• 16: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 17: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 18: M. Naor , L. J. Schulman , A. Srinivasan, Splitters and near-optimal derandomization, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.182, October 23-25, 1995
• 19: Ngo, H. Q., and Du, D. Z. 2000. A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening. DIMACS Series on Discrete Mathematics Theoretical Compuer Science, vol. 55. Amer. Math. Soc., 171--182.
• 20: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 21: Petr Slavík, A tight analysis of the greedy algorithm for set cover, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.435-441, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237991]
• 22: Aravind Srinivasan, Improved Approximation Guarantees for Packing and Covering Integer Programs, SIAM Journal on Computing, v.29 n.2, p.648-670, Oct. 1999 [doi>10.1137/S0097539796314240]
• 23: J. van Leeuwen, Graph algorithms, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
k-restriction, Derandomization, Set-Cover, almost k-wise independence, generalized hashing, group testing, splitter