Approximation algorithms for bicriteria optimization

مرکز و کتابخانه مطالعات اسلامی به زبان های اروپایی

منو

" Approximation algorithms for bicriteria optimization "
Mohammad Sarwat S. Kapoor

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 optimization\ Mohammad 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 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.
Subject	:	Applied sciences; Approximation algorithms; Bicriteria; Computer science; 0984:Computer science
Added Entry	:	S. Kapoor
Added Entry	:	Illinois Institute of Technology