Probabilistic Approaches in Combinatorial Optimization

组合优化中的概率方法

• 批准号: 0208005
• 负责人: Aravind Srinivasan
• 金额: $ 20.34万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-06-01 至 2006-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0208005&HistoricalAwards=false
• 关键词: Probabilistic; Approaches; 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.

几个计算上的离散优化问题具有自然的底层离散结构：例如，网络中的设计/路由问题有适当的图论公式。离散/组合优化是研究这种组合基础如何帮助更好地理解和解决优化问题。本项目旨在为该领域的特定重要问题开发改进算法，并为组合优化开发通用算法范例;随机性在计算环境中所起的重要作用一直是计算机科学基础中的重大发现之一。本项目提出为一类困难的组合优化问题开发改进的随机算法。问题，并在此过程中开发新的独立利益的概率工具。它也旨在进行有限的概率（即，本研究的两个子课题是研究网络领域中出现的硬优化问题和通过适当的近似算法来处理困难问题。本项目的目标是研究基本问题的改进算法方法（如网络中的各种设计、路由和调度问题）以及一般地开发改进的概率/算法范例。这一奋进将有助于开发网络和组合优化中随机/近似算法的设计、分析和工程的新原则。