In this paper we extend the knowledge on the problem of empirically searching for sorting networks of minimal depth. We present new search space pruning techniques for the last four levels of a candidate sorting network by considering only the output set representation of a network. We present an algorithm for checking whether an @math -input sorting network of depth @math exists by considering the minimal up to permutation and reflection itemsets at each level and using the pruning at the last four levels. We experimentally evaluated this algorithm to find the optimal depth sorting networks for all @math .
Bundala @cite_7 presented a computer assisted proof for the optimal depths of networks with eleven to sixteen (inclusive) inputs. He also managed to significantly reduce the number of candidates for the second layer in comparison to Parberry's approach, by considering only networks whose outputs are minimal representative up to permutation and reflection. Similar work for the second level is also presented by Michael Codish in @cite_3 . Bundala's algorithm for finding sorting networks of optimal depth is based on a SAT encoding of the optimal depth sorting networks problem, which uses the set of candidate two-layer networks as a fixed entry point. Some extra pruning techniques are presented and they use a state of the art SAT solver to find the optimal depth sorting networks for all @math .
@cite_3 @cite_7
1726079515 1769744536 2155720305 2079669094
We prove depth optimality of sorting networks from "The Art of Computer Programming".Sorting networks posses symmetry that can be used to generate a few representatives.These representatives can be efficiently encoded using regular expressions.We construct SAT formulas whose unsatisfiability is sufficient to show optimality.Resulting algorithm is orders of magnitude faster than prior work on small instances. We solve a 40-year-old open problem on depth optimality of sorting networks. In 1973, Donald E. Knuth detailed sorting networks of the smallest depth known for n ź 16 inputs, quoting optimality for n ź 8 (Volume 3 of "The Art of Computer Programming"). In 1989, Parberry proved optimality of networks with 9 ź n ź 10 inputs. We present a general technique for obtaining such results, proving optimality of the remaining open cases of 11 ź n ź 16 inputs. Exploiting symmetry, we construct a small set R n of two-layer networks such that: if there is a depth-k sorting network on n inputs, then there is one whose first layers are in R n . For each network in R n , we construct a propositional formula whose satisfiability is necessary for the existence of a depth-k sorting network. Using an off-the-shelf SAT solver we prove optimality of the sorting networks listed by Knuth. For n ź 10 inputs, our algorithm is orders of magnitude faster than prior ones. A complete set of filters @math for the optimal-depth @math -input sorting network problem is such that if there exists an @math -input sorting network of depth @math then there exists one of the form @math for some @math . Previous work on the topic presents a method for finding complete set of filters @math and @math that consists only of networks of depths one and two respectively, whose outputs are minimal and representative up to permutation and reflection. We present a novel practical approach for finding a complete set of filters @math containing only networks of depth three whose outputs are minimal and representative up to permutation and reflection. In previous work, we have developed a highly efficient algorithm for finding extremal sets ( i.e. outputs of comparator networks; itemsets; ) up to permutation. In this paper we present a modification to this algorithm that identifies the representative itemsets up to permutation and reflection. Hence, the here presented practical approach is the successful combination of known theory and practice that we apply to the domain of sorting networks. For all @math , we empirically compute the complete set of filters @math of the representative minimal up to permutation and reflection @math -input networks of depth three. Previous work identifying depth-optimal n-channel sorting networks for 9 a#x2264; n a#x2264; 16 is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until n = 40. In a seminal paper, Karp, Vazirani, and Vazirani show that a simple ranking algorithm achieves a competitive ratio of 1-1 e for the online bipartite matching problem in the standard adversarial model, where the ratio of 1-1 e is also shown to be optimal. Their result also implies that in the random arrivals model defined by Goel and Mehta, where the online nodes arrive in a random order, a simple greedy algorithm achieves a competitive ratio of 1-1 e. In this paper, we study the ranking algorithm in the random arrivals model, and show that it has a competitive ratio of at least 0.696, beating the 1-1 e ≈ 0.632 barrier in the adversarial model. Our result also extends to the i.i.d. distribution model of , removing the assumption that the distribution is known. Our analysis has two main steps. First, we exploit certain dominance and monotonicity properties of the ranking algorithm to derive a family of factor-revealing linear programs (LPs). In particular, by symmetry of the ranking algorithm in the random arrivals model, we have the monotonicity property on both sides of the bipartite graph, giving good "strength" to the LPs. Second, to obtain a good lower bound on the optimal values of all these LPs and hence on the competitive ratio of the algorithm, we introduce the technique of strongly factor-revealing LPs. In particular, we derive a family of modified LPs with similar strength such that the optimal value of any single one of these new LPs is a lower bound on the competitive ratio of the algorithm. This enables us to leverage the power of computer LP solvers to solve for large instances of the new LPs to establish bounds that would otherwise be difficult to attain by human analysis.