• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Liao, Kewen (Liao, Kewen.) [1] | Shen, Hong (Shen, Hong.) [2] | Guo, Longkun (Guo, Longkun.) [3] (Scholars:郭龙坤)

Indexed by:

CPCI-S EI Scopus SCIE

Abstract:

In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most R-i facilities with opening cost f(i). Each client j requires an allocation of r(j) open facilities and connecting j to any facility at site i incurs a connection cost c(ij). The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA(infinity)) [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] problems: for every site i, FTRA(infinity) does not have the constraint R-i, whereas FTFL sets R-i = 1. These problems are said to be uniform if all r(j)'s are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1.7245 from [3]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O (n(4)) time, where n is the total number of sites and clients. (C) 2015 Elsevier B.V. All rights reserved.

Keyword:

Approximation algorithms LP-rounding Primal-dual Reduction Resource allocation Time complexity

Community:

  • [ 1 ] [Liao, Kewen]Univ Adelaide, Sch Comp Sci, Adelaide, SA, Australia
  • [ 2 ] [Shen, Hong]Univ Adelaide, Sch Comp Sci, Adelaide, SA, Australia
  • [ 3 ] [Shen, Hong]Sun Yat Sen Univ, Sch Comp & Informat Technol, Guangzhou 510275, Guangdong, Peoples R China
  • [ 4 ] [Guo, Longkun]Fuzhou Univ, Sch Math & Comp Sci, Fuzhou 350002, Peoples R China

Reprint 's Address:

  • [Shen, Hong]Univ Adelaide, Sch Comp Sci, Adelaide, SA, Australia

Show more details

Related Keywords:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2015

Volume: 590

Page: 118-128

0 . 6 4 3

JCR@2015

0 . 9 0 0

JCR@2023

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:175

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 2

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:13/10057765
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1