Mathematical Sciences: Ideal Clutters and Binary Materials in Combinatrial Optimization

数学科学：组合优化中的理想杂波和二元材料

• 批准号: 9409274
• 负责人: Beth Novick
• 金额: $ 1.8万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-06-15 至 1996-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9409274&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Ideal; Clutters; Binary

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. ***

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