Using Nondeterminism to Design Efficient Deterministic Algorithms

In this paper we illustrate how nondeterminism can be usedconveniently and effectively in designing efficient deterministicalgorithms. In particular, our method gives a parameterizedalgorithm of running time O((5.7 k)^k n) for the 3-D matchingproblem, which significantly improves the previous algorithm byDowney et al. The algorithm can be generalized toyield an improved algorithm for the r-D matching problem for anypositive integer r. The method can also be employed in designingdeterministic algorithms for other optimization problems as well.