Algorithms for some combinatorial problems

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

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.