This is an investigation of combinatorial optimization problems involving multiple objectives. Such problems arise in a variety of application areas including communication networks, very large scale integrated systems, facility location and management of hazardous materials. For many such problems, even optimizing one objective is often computationally intractable. Motivated by the practical importance of these problems, the focus of this research is on developing efficient algorithms that produce solutions which are near-optimal with respect to all the objectives. The major goals of the proposed research include identifying classes of multiobjective optimization problems from various application areas, developing efficient approximation algorithms for the problems and evaluating their performance through analysis/experimentation, developing a software library of multiobjective approximation algorithms that can be used by researchers and practitioners, and obtaining insights into the intrinsic difficulties encountered in developing approximation algorithms for multiobjective problems. Both graduate and undergraduate students will be encouraged to participate in this work. The results obtained will be incorporated into seminar courses suitable for graduate and advanced undergraduate students. A number of practical situations require a careful analysis of constraints and objectives. For example, a business organization may want to upgrade the communication network interconnecting its branches so that information can be exchanged among the branches at a faster rate. Often, only a limited budget is available for the upgrade. It is of interest to the organization to obtain the best possible upgrade whose cost is within the available budget. Such situations involving constraints and objectives arise in a number of contexts including determining appropriate locations for facilities (such as hospitals, fire stations, etc.) and management of hazardous materials. Ma thematically, the problems arising in these contexts can be expressed as optimization problems involving multiple objectives. However, computing the best solutions to such problems is often infeasible. The focus of this research is on developing procedures that can quickly compute solutions which are close to the best solutions with respect to all the objectives. The research will investigate problems from a number of application areas. One of the goals of this research is to develop a library of software procedures that can be used by both practitioners and researchers.
