Set covering polyhedra graphs, and matroids

集合覆盖多面体图和拟阵

• 批准号: 238811-2006
• 负责人: Guenin, Bertrand
• 金额: $ 2.19万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=363368
• 关键词: Set; covering; polyhedra; graphs; matroids

My primary area of interest is combinatorial optimization, in particular the integer programming models known as packing and covering. A wide variety of practical questions can be formulated in this setting and include: scheduling problems, assignment problems, and the problem of shipping one or more commodities across a network. Sometimes, owing to the special structure of the problem, the natural linear programming relaxation yields an optimal solution. When this occurs the problem can be solved efficiently. The focus of my research has been to characterize when this phenomenon occurs. Although these models have their roots in real life, this leads to deep questions of a purely mathematical nature.

我的主要兴趣领域是组合优化，特别是被称为包装和覆盖的整数规划模型。各种各样的实际问题可以在这种设置中制定，包括：调度问题，分配问题，以及在网络上运送一个或多个商品的问题。有时，由于问题的特殊结构，自然的线性规划松弛会产生最优解。当这种情况发生时，问题可以有效地解决。我的研究重点是描述这种现象发生的时间。虽然这些模型都植根于真实的生活中，但这导致了纯数学性质的深层问题。