Randomized Post-optimization for t-Restrictions

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.