High Quality Discrete Algorithms Based on Engineering Criteria

点击翻译按钮获取中文摘要

Discrete algorithms have been evaluated by the unique measure 'asymptotic time complexity' for many cases. Recently, however, many other measures have been proposed, e.g., the approximation ratios for solving combinatorial problems approximately, and the competitive ratios for solving online problems in which we have no information on the future inputs. In this research, we studied these new measures as the criteria based on engineering requirements, and developed the methodologies for qualifying algorithms from this point of view.As to the stable marriage problems, it is known to be solvable in polynomial time. We have generalized the problem, and proved that it is also solvable in polynomial time even when ties in the lists or incomplete lists are allowed. While we proved the intractability for the case both ties and incompleteness are allowed, we proposed an approximation algorithm that achieves an approximation ratio less than 2.As to the satisfiability problems, we developed a 1.324^n algorithm for 3-SAT by complementarily combining two types of algorithms based on, the local search and the backtracking. We also considered condensing the density (i.e., the ratio of satisfying assignments to the 2^n assignments) of formulas.Other research topics are as follows ; online algorithms, network algorithms, quantum algorithms.