(A) This project focuses on the design and analysis of efficient algorithms for network and combinatorial optimization problems. In particular, the project concentrates on (1) theoretical analysis and experimental evaluation of algorithms and (2) algorithmic challenges that arise in applications such as telecommunication networks and information management. Specifically at AT&T, development of new and enhanced communication and information services necessitates algorithmic research and formulation of new models and problems. (B) A principal component of the project is the design of fast algorithms for fundamental network problems (such as shortest path flow computations, and transitive closure). For large problem instances where a quadratic time exact algorithm is infeasible, approximate linear time algorithms are investigated, by considering these well known problems in new contexts. For example, availability of multi-processor systems warrants development of parallel and distributed algorithms, and large interactive databases necessitate the design of dynamic and online algorithms. (C) This award enables the PI to visit the Department of Computer Science, University of California, Berkeley for six months, so that fruitful collaborations with faculty and graduate students can be initiated. In particular, her activities include (3) the development and teaching of a graduate course in network algorithms and combinatorial optimization, and (4) an outreach program to women and other under represented groups. It is anticipated that this university/industrial collaborative effort will be continued at both Berkeley and AT&T Laboratories.***
