Presidential Young Investigator Award: Combinatorial Issues in Large-Scale Network Design

总统青年研究员奖：大规模网络设计中的组合问题

• 批准号: 9057665
• 负责人: Daniel Bienstock
• 金额: $ 17.47万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-07-01 至 1996-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9057665&HistoricalAwards=false
• 关键词: Presidential; Young; Investigator; Award; Combinatorial

Research concerns the design and analysis of algorithms for discrete optimization problems, and the study of discrete structures in general. Two areas of special interest are: (1) the study of certain "obstructions", called tangles, to small tree- or path-width, which play a crucial role in the Graph Minors theory; and (2) to investigate a problem of interest in VLSI (very large system integration) chip and communication network switch design, involving the minimum number of edge crossings when drawing a graph in the plane. There are several open problems concerning crossing numbers, one of the most important being their efficient approximation (there are no known results, either positive or negative). The tools from the theory of arrangements will be employed.

研究涉及离散优化问题的算法设计和分析，以及一般的离散结构研究。两个特别感兴趣的领域是：(1)研究小树或路径宽度的某些“障碍物”，称为缠结，这在图小次理论中起着至关重要的作用；(2)研究VLSI（超大系统集成）芯片和通信网络交换机设计中感兴趣的问题，涉及在平面上绘制图形时的最小边交叉数。有几个关于交叉数的开放问题，其中最重要的是它们的有效近似（没有已知的结果，无论是正的还是负的）。我们将使用安排理论中的工具。