Probabilistic Approaches in Combinatorial Optimization

一些计算上的离散优化问题具有自然的离散结构：例如，网络中的设计/布线问题具有适当的图论公式。离散/组合优化是研究这种组合基础如何帮助人们更好地理解和解决优化问题。本项目旨在为这一领域中的特殊问题开发改进的算法，并为组合优化开发通用的算法范例；随机性在计算环境中所起的强大作用是计算机科学基础中的重大发现之一。这个项目建议为一类困难的组合优化问题开发改进的随机化算法，并开发在这个过程中独立的新的概率工具。还旨在对其中一些相关的问题进行重新的概率分析(即平均情况而不是最坏情况)。本研究的两个子主题是研究网络时代出现的硬优化问题，这个项目的目标是研究基本问题(如网络中的各种设计、路由和调度问题)的改进算法方法，并开发改进的概率/算法范例。这一努力将有助于为网络和组合优化中的随机/近似算法的设计、分析和工程设计提供新的原则。

Several computationally di .cult optimization problems have a natural underlying discrete struc-ture:e.g.,design/routing problems in networking have appropriate graph-theoretic formulations.Discrete/combinatorial optimization is the study of how such combinatorial underpinnings can helpus understand better and solve optimization problems.This project aims to develop improved algorithms for speci .c important problems in this .eld,and to develop general algorithmic paradigms for combinatorial optimization;one of the main gen-eral approaches will be probabilistic The powerful role played by randomness in the computationalcontext has been among the major discoveries in the foundations of computer science.This projectproposes to develop improved randomized algorithms for a family of hard combinatorial optimiza-tion problems,and to develop new probabilistic tools of independent nterest in the process.It alsoaims to conduct re .ned probabilistic (i.e.,average-case instead of worst-case)analyses of some ofthese problems where relevant.Two sub-themes of the proposed research are to study hard opti-mization problems that arise in the .eld of networking,and to approach di .cult problems throughapproximation algorithms where appropriate.The goal of this project is to study improved algorithmic approaches for fundamental problems(such as various design,routing,and scheduling problems in networks)as well as to develop improvedprobabilistic/algorithmic paradigms in general.This endeavor will help develop new principles forthe design,analysis,and engineering of randomized/approximation algorithms in networking andcombinatorial optimization.