Algorithms for some combinatorial problems

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

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.