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

点击翻译按钮获取中文摘要

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.