BICRITERIA NETWORK DESIGN-PROBLEMS

We study a general class of bicriteria network design problems. A gene ric problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost functions), with a budget specified on the first objective, find a subgraph from a given subgraph-class that minimizes the second objective subject to the budg et on the first objective. We consider three different criteria - the total edge cost, the diameter, and the maximum degree of the network. Here, we present the first polynomial-time approximation algorithms fo r a large class of bicriteria network design problems for the previous ly mentioned criteria. The following general types of results are pres ented. First, we develop a framework for bicriteria problems and their approximations. Second, when the two criteria are the same we present a ''black box'' parametric search technique. This black box takes in as input an (approximation) algorithm for the unicriterion situation a nd generates an approximation algorithm for the bicriteria case with o nly a constant factor loss in the performance guarantee. Third, when t he two criteria are the diameter and the total edge costs we use a clu ster-based approach to devise a approximation algorithms - the solutio ns output violate both the criteria by a logarithmic factor. Finally, for the class of treewidth-bounded graphs, we provide pseudo-polynomia l-time algorithms for a number of bicriteria problems using dynamic pr ogramming. We show how these pseudo-polynomial-time algorithms can be converted to fully polynomial-time approximation schemes using a scali ng technique. (C) 1998 Academic Press.