Conference Proposal: CRM Theme Semester on Combinatorial Optimization (June 2006 - December 2006)

会议提案：组合优化 CRM 主题学期（2006 年 6 月 - 2006 年 12 月）

• 批准号: 0607951
• 负责人: Michel Goemans
• 金额: $ 3万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-05-01 至 2007-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0607951&HistoricalAwards=false
• 关键词: Conference; Proposal; CRM; Theme; Semester

The Centre de Recherches Mathematiques in Montreal (CRM) is organizing aTheme Semester on Combinatorial Optimization that will include a NATOAdvanced Study Institute and five workshops. Broadly speaking, combinatorial optimization is the study of optimization problems in which there are a finite (but usually very large) number of potentialsolutions, also called feasible solutions. These are not enumerated but rather defined implicitly by constraints, i.e., linear ornonlinear relations. For instance, the famous traveling salesman problem (TSP) consists of selecting the least expensive tour of a given set oflocations, and the minimum spanning tree problem (MST) of selecting theleast expensive network connecting given sites. Combinatorial optimization has been applied to many fields of huge practical import, such as transport scheduling, telecommunications planning and circuit design (where problems similar to the TSP, among others, must be solved routinely). Since most combinatorial optimization problems are verydifficult to solve, researchers have, on the one hand, improved thetime-consuming algorithms that compute optimal solutions of difficultproblems such as the TSP, and on the other, designed efficientalgorithms that compute near-optimal solutions (also called heuristicsolutions). Two of the workshops will address the design of such algorithms (from different angles). The three others will address the computation of polyhedra related to optimization, the use of optimization in data mining, and the design of computer and communication networks such as the Internet.

蒙特利尔数学研究中心 (CRM) 正在组织一个关于组合优化的主题学期，其中包括一个北约高级研究所和五个研讨会。从广义上讲，组合优化是对优化问题的研究，其中存在有限（但通常非常大）数量的潜在解决方案，也称为可行解决方案。这些不是枚举的，而是通过约束隐式定义的，即线性或非线性关系。例如，著名的旅行商问题（TSP）包括选择一组给定位置的最便宜的旅行，以及选择连接给定站点的最便宜的网络的最小生成树问题（MST）。组合优化已应用于许多具有巨大实际意义的领域，例如传输调度、电信规划和电路设计（其中类似于TSP的问题必须常规解决）。由于大多数组合优化问题都很难解决，研究人员一方面改进了计算 TSP 等困难问题最优解的耗时算法，另一方面设计了计算近最优解（也称为启发式解）的高效算法。其中两个研讨会将讨论此类算法的设计（从不同角度）。另外三个将讨论与优化相关的多面体计算、优化在数据挖掘中的应用以及计算机和通信网络（例如互联网）的设计。