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.