<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Publication:
The approximability of multiple facility location on directed networks with random arc failures

Loading...
Thumbnail Image

Departments

Item type:Organizational Unit,

School / College / Institute

Item type:Organizational Unit,

Program

Organization Authors

Co-Authors

Hassin, Refael

Ravi, R.

Segev, Danny

Date

Language

Embargo Status

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

We introduce and study the maximum reliability coverage problem, where multiple facilities are to be located on a network whose arcs are subject to random failures. Our model assumes that arcs fail independently with non-uniform probabilities, and the objective is to locate a given number of facilities, aiming to maximize the expected demand serviced. In this context, each demand point is said to be serviced (or covered) when it is reachable from at least one facility by an operational path. The main contribution of this paper is to establish tight bounds on the approximability of maximum reliability coverage on bidirected trees as well as on general networks. Quite surprisingly, we show that this problem is NP-hard on bidirected trees via a carefully-constructed reduction from the partition problem. On the positive side, we make use of approximate dynamic programming ideas to devise an FPTAS on bidirected trees. For general networks, while maximum reliability coverage is (1-1/e+epsilon)-inapproximable as an extension of the maxk-cover problem, even estimating its objective value is #P-complete, due to generalizing certain network reliability problems. Nevertheless, we prove that by plugging-in a sampling-based additive estimator into the standard greedy algorithm, a matching approximation ratio of 1-1/e-epsilon can be attained.

Source

Publisher

Springer

Citation

item.page.haspartof

Source

Algorithmica

item.page.ispartofseries

item.page.edition

DOI

10.1007/s00453-020-00693-8

item.page.datauri

item.page.link

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

Related Patent

Related Goal

Google Scholar
Scholar'da Ara ↗
Altmetric
Dimensions
PlumX Metrikleri
BIP! Indicators