Abstract
Search, test, and measurement problems in sparse domains often require the construction of arrays in which every t or fewer columns satisfy a simply stated combinatorial condition. Such t-restriction problems often ask for the construction of an array satisfying the t-restriction while having as few rows as possible. Combinatorial, algebraic, and probabilistic methods have been brought to bear for specific t-restriction problems; yet in most cases they do not succeed in constructing arrays with a number of rows near the minimum, at least when the number of columns is small. To address this, an algorithmic method is proposed that, given an array satisfying a t-restriction, attempts to improve the array by removing rows. The key idea is to determine the necessity of the entry in each cell of the array in meeting the t-restriction, and repeatedly replacing unnecessary entries, with the goal of producing an entire row of unnecessary entries. Such a row can then be deleted, improving the array, and the process can be iterated. For certain t-restrictions, it is shown that by determining conflict graphs, entries that are necessary can nonetheless be changed without violating the t-restriction. This permits a richer set of ways to improve the arrays. The efficacy of these methods is demonstrated via computational results.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ahlswede, R., Deppe, C., Lebedev, V.: Threshold and Majority Group Testing. In: Aydinian, H., Cicalese, F., Deppe, C. (eds.) Ahlswede Festschrift. LNCS, vol. 7777, pp. 488–508. Springer, Heidelberg (2013)
Ahlswede, R., Wegener, I.: Search Problems. Wiley Interscience (1987)
Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms 2, 153–177 (2006)
Colbourn, C.J.: Constructing perfect hash families using a greedy algorithm. In: Li, Y., Zhang, S., Ling, S., Wang, H., Xing, C., Niederreiter, H. (eds.) Coding and Cryptology, pp. 109–118. World Scientific, Singapore (2008)
Colbourn, C.J.: Distributing hash families and covering arrays. J. Combin. Inf. Syst. Sci. 34, 113–126 (2009)
Colbourn, C.J.: Covering arrays and hash families, Information Security and Related Combinatorics. In: NATO Peace and Information Security, pp. 99–136. IOS Press (2011)
Colbourn, C.J., Horsley, D., Syrotiuk, V.R.: Strengthening hash families and compressive sensing. Journal of Discrete Algorithms 16, 170–186 (2012)
Colbourn, C.J., Zhou, J.: Improving two recursive constructions for covering arrays. Journal of Statistical Theory and Practice 6, 30–47 (2012)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press (2009)
Du, D.-Z., Hwang, F.K.: Combinatorial group testing and its applications, 2nd edn. World Scientific Publishing Co. Inc., River Edge (2000)
Karp, R.M., Miller, R.E., Thatcher, J.W.: Reducibility among combinatorial problems. Journal of Symbolic Logic 40(4), 618–619 (1975)
Liu, L., Shen, H.: Explicit constructions of separating hash families from algebraic curves over finite fields. Designs, Codes and Cryptography 41, 221–233 (2006)
Nayeri, P., Colbourn, C.J., Konjevod, G.: Randomized Postoptimization of Covering Arrays. In: Fiala, J., Kratochvíl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol. 5874, pp. 408–419. Springer, Heidelberg (2009)
Nayeri, P., Colbourn, C.J., Konjevod, G.: Randomized postoptimization of covering arrays. European Journal of Combinatorics 34, 91–103 (2013)
Stinson, D.R., Van Trung, T., Wei, R.: Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J. Statist. Plann. Infer. 86, 595–617 (2000)
Stinson, D.R., Zaverucha, G.M.: Some improved bounds for secure frameproof codes and related separating hash families. IEEE Transactions on Information Theory, 2508–2514 (2008)
Walker II, R.A.: Phftables, http://www.phftables.com (accessed March 10, 2012)
Walker II, R.A., Colbourn, C.J.: Perfect hash families: Constructions and existence. Journal of Mathematical Cryptology 1, 125–150 (2007)
Yato, T., Seta, T.: Complexity and completeness of finding another solution and its application to puzzles. IEICE - Transactions on Fundamentals of Electronics, Communications and Computer Sciences E86-A(5), 1052–1060 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Colbourn, C.J., Nayeri, P. (2013). Randomized Post-optimization for t-Restrictions. In: Aydinian, H., Cicalese, F., Deppe, C. (eds) Information Theory, Combinatorics, and Search Theory. Lecture Notes in Computer Science, vol 7777. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36899-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-36899-8_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36898-1
Online ISBN: 978-3-642-36899-8
eBook Packages: Computer ScienceComputer Science (R0)