Studies on Realistic Solutions to Theoretically Hard Problems

在这项研究中，我们一直致力于在算法理论中流行的渐近分析的传统框架下，被认为是计算困难的几个问题。更具体地说，我们研究了用于印刷的最佳网点图案的设计问题和聚类问题。对于前一个问题，我们已经注意到，差异理论可以应用于这个问题。差异理论得到了严谨的研究，并取得了许多重要的理论成果。将其与图论中的匹配概念相结合，成功地改进了所得解的性能。由于我们也得到了令人满意的实验结果，我们打算将结果提交给一些杂志。对于聚类问题，我们将一种算法方法应用于图像数据库上的图像查询系统中，取得了比传统方法更好的实验结果。我们正计划在不久的将来提交给一些国际期刊的一篇论文中总结这些结果。

In this study we have been engaged in several problems which were thought to be computationally Hard within the traditional framework of asymptotic analysis popular in the theory of algorithms. More concretely, we have studied the problem of designing optimal dot patterns for printing and that of clustering. For the former problem, we have noticed that the discrepancy theory can be applied to the problem. The discrepancy theory has been rigorously studied and is full of important theoretical results. Combining it with the notion of matching in the graph theory, we have succeeded in improving the performance of the solutions obtained. Since we also had satisfactory experimental results, we intend to submit the result to some journal. For the problem of clustering, we have applied an algorithmic approach to image query system On image database with good experimental results that exceed results by traditional Approaches. We are planning to summarize the results in a paper to be submitted to some International journal in near future.