Probabilistic Approaches in Combinatorial Optimization

几个计算di。Cult优化问题具有自然的潜在离散结构。，网络中的设计/路由问题有适当的图论公式。离散/组合优化是研究这些组合基础如何帮助我们更好地理解和解决优化问题。本项目旨在开发改进的算法，以解决这方面的特定重要问题。并开发组合优化的通用算法范式；随机在计算环境中所起的强大作用是计算机科学基础的重大发现之一。本项目提出为一系列难组合优化问题开发改进的随机算法，并在此过程中开发新的独立感兴趣的概率工具。它还旨在引导re。在相关的情况下对其中一些问题进行概率分析（即，平均情况而不是最坏情况）。提出的研究的两个子主题是研究的困难优化问题，出现在。网络的领域，并接近di。在适当的情况下，通过近似算法解决邪教问题。该项目的目标是研究解决基本问题（如网络中的各种设计、路由和调度问题）的改进算法方法，以及总体上开发改进的概率/算法范例。这一努力将有助于为网络和组合优化中的随机/近似算法的设计、分析和工程开发新的原则。

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.