Probabilistic Approaches in Combinatorial Optimization

University Of Maryland, College Park, College Park MD

Investigators

Abstract

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 help us 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 computational context has been among the major discoveries in the foundations of computer science.This project proposes 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 also aims to conduct re .ned probabilistic (i.e.,average-case instead of worst-case)analyses of some of these 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 through approximation 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 improved probabilistic/algorithmic paradigms in general.This endeavor will help develop new principles for the design,analysis,and engineering of randomized/approximation algorithms in networking and combinatorial optimization.