Mathematical Sciences: Ideal Clutters and Binary Materials in Combinatrial Optimization

本文讨论了组合优化、图论、拟阵理论和编码理论之间的联系。拟阵推广了向量空间的概念。理想杂波是在集覆盖问题中出现的一类0-1矩阵。集合覆盖问题的应用包括航空公司机组调度、卡车调度和设施选址。码理论被用来有效地解释发送、接收和解码信息时的噪声。二进制杂波出现在许多图论设置和网络应用中。二元杂波、拟阵和码之间有着密切的联系。申请人拟在矩阵环境下研究理想二元杂波的结构，并确定用矩阵方法解决一个长期存在的图着色问题和一些涉及某些码的覆盖半径的问题的可行性。码的覆盖半径对解码很重要。规划活动将包括与两位高级研究人员合作，他们是格勒诺布尔中国核研究中心的Andras Sebo和克莱姆森大学的J.D. Key。计划期的结果将是几篇论文和一份正式的NSF提案，将在开始日期后的18个月内完成。＊＊＊

9409274 Novick This proposal deals with connections between combinatorial optimization, graph theory, matroid theory and coding theory. Matroids generalize the notion of vector space. An ideal clutter is a type of 0-1 matrix which arises in the set covering problem. Applications of the set covering problem include airline crew scheduling, dispatching of trucks and facility location. The theory of codes is used to efficiently account for noise when sending, receiving and decoding messages. Binary clutters occur in many graph theoretic settings and in network applications. There are close connections between binary clutters, matroids and codes. The applicant proposes to study the structure of ideal, binary clutters in a matroidal context and to determine the feasibility of a matroidal approach to a long standing graph colouring problem and to some questions involving the covering radius of certain codes. The covering radius of a code is important for decoding. Planning activities will include working with two senior researchers, Andras Sebo, of CNRC in Grenoble, and J.D. Key of Clemson University. The outcome of the planning period will be several papers and a formal NSF proposal to be completed within 18 months of the start date. ***