Algorithms for some combinatorial problems

我研究的主要主题是研究解决组合问题的算法。组合学与计算机科学的许多领域有关，包括密码学、通信网络和生物信息学。为了集中我的研究，我将研究以下内容：1)k-超图的度序列，以及2)多层合作搜索和组合设计。k-超图的度序列研究是超图理论中一个重要的开放问题。虽然很多人已经研究了这个问题，但是对于k-超图的有效度序列的多面体还没有已知的简单表征。这样的描述将是一个重大突破。我建议使用我最近发现的一个线性时间算法来研究3-超图的有效度序列的多面体。通过应用这个算法，我希望能找到关于这个多面体的新信息。在第二个项目中，我提议研究多层协同搜索策略在组合设计理论衍生的优化问题中的应用。这是一种解决组合设计优化问题的新方法，其性能通常优于遗传算法、模拟退火和禁忌搜索等元启发式搜索技术。最近，我将多层协同搜索策略应用于覆盖设计问题，发现它的性能非常好，可以发现一些新的搜索结果。我建议研究为什么多层合作搜索比元启发式搜索（如模拟退火和禁忌搜索）更好，对于某些覆盖设计问题实例，并希望确定这种搜索方法将表现良好的条件。此外，我想研究将多层协同搜索应用于其他组合设计优化问题的可能性，如拉丁方格、t型设计和lotto设计。

The main theme of my research is the study of algorithms for solving combinatorial problems.  Combinatorics is relevant in many areas of computer science including cryptography, communication networks and bio-informatics.  To focus my research,  I will investigate the following: 1) degree sequences for k-hypergraphs, and 2) multilevel cooperative search and combinatorial designs.   The study of degree sequences for k-hypergraphs is an important open problem in hypergraph theory.  Although many people have studied this problem, there is no known simple characterization of the polytope of valid degree sequences for k-hypergraphs.  Such a characterization would be a major breakthough.  I propose to study the polytope  of valid degree sequences of 3-hypergraphs using an a linear-time algorithm that I have recently discovered.  By applying the algorithm, I hope to find new information about this polytope. In the second project, I propose to investigate the application of the multilevel cooperative search strategy to optimization problems derived from combinatorial design theory.  This is a new approach to solving combinatorial design optimization problems, and it often performs better than meta-heuristic search techniques such as genetic algorithms, simulated annealing and tabu search.  Recently, I applied the multilevel cooperative search strategy to the covering design problem and noticed that it performed very well as was able to discover some new results with this search strategy.  I propose to investigate why the multilevel cooperative search works better than meta-heuristic searchs such as simulated annealing and tabu search, for certain covering design problem instances and hope to determine conditions under which this search method will perform well.  In addition, I would like to investigate the possibility of applying the multilevel cooperative search to other combinatorial design optimization problems, such as Latin squares, t-designs and lotto designs.