  Document Type  :  Latin Dissertation  Language of Document  :  English  Record Number  :  54431  Doc. No  :  TL24385  Call number  :  3203062  Main Entry  :  Mohammad Sarwat  Title & Author  :  Approximation algorithms for bicriteria optimizationMohammad Sarwat  College  :  Illinois Institute of Technology  Date  :  2005  Degree  :  Ph.D.  student score  :  2005  Page No  :  105  Abstract  :  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 NPhard 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 NPhard 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 primaldual approximation scheme. We further generalize this algorithm to solve the edge capacity version and piecewise linear profit version of the problem.  Subject  :  Applied sciences; Approximation algorithms; Bicriteria; Computer science; 0984:Computer science  Added Entry  :  S. Kapoor  Added Entry  :  Illinois Institute of Technology 
     
   
http://lib.clisel.com/site/catalogue/54431

 