Algorithms for some combinatorial problems

一些组合问题的算法

• 批准号: 250389-2006
• 负责人: Li, Ben
• 金额: $ 0.73万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2006
• 资助国家: 加拿大
• 起止时间: 2006-01-01 至 2007-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=338425
• 关键词: Algorithms; some; combinatorial; problems

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.

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