Approximation algorithms for bicriteria optimization

In a typical optimization problem in a network, the goal is to optimize an incurred cost, while meeting a structural requirement. For example, in steiner tree problem, the structural requirement is to connect all the terminals and the incurred cost is the sum of the cost of all the edges included in the solution. However, we sometimes have to optimize two different measures. This kind of optimization is called Bicriteria Optimization. In order to efficiently solve such problems we use Approximation Algorithms that are guaranteed to provide a solution close to the optimum within a certain bound.; We consider optimization problems where, apart from the structural requirement, an additional constraint has been placed. This additional constraint is in the form of a budget on a secondary cost. We consider four sets of such problems in this thesis.; The first is the Bounded Diameter Minimum Cost Steiner Tree (BDMST) problem, and its various special cases. It is NP-hard to even approximate this problem with a factor better than O(log n). We provide an approximation algorithm for the most general case with an (O( p log s/log p), O(log s/log p)) approximation ratio, where s is the number of terminals and p is an input parameter. We further improve the approximation for various special cases.; We also present an approximation algorithm for Bounded Diameter Minimum Cardinality Edge Addition problem (BDMC). This too, is an NP-hard problem. We present an algorithm with O(2, log n) approximation guarantee.; We further present an approximation algorithm for the Bounded Hops Minimum Power Broadcast problem. This problem is analogous to the Bounded Diameter Minimum Cost Spanning Tree problem in conventional networks. The approximation ratio is (O(log n), O(log n)). We show how to modify the algorithm to handle other structural requirements and present improvements for geometric cases.; Finally, we present a bicriteria generalization of the Transportation Problem: Budgeted Transportation. We then present an efficient, auction based primal-dual approximation scheme. We further generalize this algorithm to solve the edge capacity version and piece-wise linear profit version of the problem.