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.