组合与优化哲学博士-离散优化

离散或组合优化体现了与许多相关主题相联系的广阔而重要的组合领域。其中包括线性编程
Combinatorics is the study of discrete structures and their properties. Many modern scientific advances have employed combinatorial structures to model the physical world, and recent advances in computational technology have made such investigations feasible. In particular, since computers process discrete data, combinatorics has become indispensable to computer science. Optimization, or mathematical programming, is the study of maximizing and minimizing functions subject to specified boundary conditions or constraints. With the emergence of computers, optimization experienced a dramatic growth as a mathematical theory, enhancing both combinatorics and classical analysis. The functions to be optimized arise in engineering, the physical and management sciences, and in various branches of mathematics. The PhD involves about two years of grad courses followed by research and a dissertation, and typically lasts four years.<br><br>Discrete or combinatorial optimization embodies a vast and significant area of combinatorics that interfaces many related subjects. Included among these are linear programming, operations research, theory of algorithms and computational complexity. Much of combinatorial optimization is motivated by very simple and natural problems such as routing problems in networks, packing and covering problems in graph theory, scheduling problems, and sorting problems. But the methodology of the subject encompasses a variety of techniques ranging from elementary tree-growing procedures to constructions of Hilbert bases of integer lattices. The growth of this area has been linked with the development of linear programming and of graph theory over the last forty years. It also has close connections with the theoretical computer science, in particular, the analysis of algorithms. Generally the problems are to find efficient methods of constructing good solutions and to find methods of measuring the solution quality. That is, we wish to be able to produce bounds on the optimum solution which enable us to assert that the error of the solution in hand is no worse than, say, 2%.