High Quality Discrete Algorithms Based on Engineering Criteria

在许多情况下，离散算法被用唯一的度量‘渐近时间复杂性’来评估。然而，最近已经提出了许多其他的度量，例如，近似地解决组合问题的近似比，以及解决我们没有关于未来输入的信息的在线问题的竞争比。在本研究中，我们研究了这些新的度量作为基于工程需求的准则，并从这个角度提出了算法的验证方法。对于稳定的婚姻问题，已知它在多项式时间内是可解的。我们推广了这一问题，并证明了即使允许列表中的关系或不完全列表，该问题在多项式时间内也是可解的。针对可满足性问题，我们提出了一种近似比小于2的近似算法，并将基于局部搜索和回溯的两种算法互补地结合起来，得到了一个1.324^n的3-SAT算法。我们还考虑了压缩公式的密度(即满意赋值与2^n赋值之比)。其他研究课题如下：在线算法、网络算法、量子算法。

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.