You are here: Computer Science > Seminars

Computer Science Seminars

  

A Distributed (R,2)-Approximation Algorithm for Fault-Tolerant Facility Location Shihong XU , Computer Science, University of Adelaide Wed, 11 Nov, 2009, 10:10 Lecture Room 2060, Computer Science, Plaza Building Abstract We propose an approximation algorithm for the problem of Fault-Tolerant Facility Location which is implemented in a distributed and asynchronous manner within O(n) rounds of communication. Here n is the number of vertices in the network. As far as we know, the performance guarantee of similar algorithms (centralized) remains unknown except a special case where all cities have a uniform connectivity requirement. In this paper, we assume the shortest-path routing scheme deployed, as well as a constant (given) size of R, which represents the distinct levels of fault-tolerant capability provided by the system (i.e. distinct connectivity requirements), and prove that the cost of our solution is no more than RF+ 2C in the general case, where F and C are respectively the facility cost and connection cost in an optimal solution. Further more, extensive numerical experiments showed that the quality of our solutions is comparable to the optimal solutions when R is no more than 10.

The Fault-Tolerant Facility Allocation Problem Shihong XU , Computer Science, University of Adelaide Wed, 11 Nov, 2009, 10:35 Lecture Room 2060, Computer Science, Plaza Building Abstract We study the problem of Fault-Tolerant Facility Allocation (FTFA) which is a relaxation of the classical Fault-Tolerant Facility Location (FTFL) problem [1]. Given a set of sites, a set of cities, and corresponding facility operating cost at each site as well as connection cost for each site-city pair, FTFA requires to allocate each site a proper number of facilities and further each city a prespeci ed number of facilities to access. The objective is to find such an allocation that minimizes the total combined cost for facility operating and service accessing. In comparison with the FTFL problem which restricts each site to at most one facility, the FTFA problem is less constrained and therefore incurs less cost which is desirable in application. In this paper, we consider the metric FTFA problem where the given connection costs satisfy triangle inequality and we present a polynomial-time algorithm with approximation factor 1.861 which is better than the best known approximation factor 2.076 for the metric FTFL problem [2].

Forthcoming Seminars Wed, 18 Nov, 10:10, John Willison and Li Jiang (Centre for Learning and Professional Development, and Computer Science), Students becoming researchers, researchers becoming renown

Recent Seminars Wed, 4 Nov, 10:10, Yidong LI (Computer Science, University of Adelaide), Equi-width Data Swapping for Private Data Publication Wed, 16 Sep, 10:10, Dylan Sale (Computer Science, University of Adelaide), SecondSkin: An interactive method for appearance transfer Wed, 9 Sep, 10:10, Dr. Lam Thu BUI (Research Associate, University of Adelaide), Multi-objective optimization using evolutionary algorithms

[ Seminars Home | List seminars for: '01 '02 '03 '04 '05 '06 '07 '08 '09 | Email Notification | Administer Future Seminars ]