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

Publication:
Multiple facility location on a network with linear reliability order of edges

Loading...
Thumbnail Image

Departments

Item type:Organizational Unit,

School / College / Institute

Item type:Organizational Unit,

Program

Organization Authors

Co-Authors

Hassin, Refael

Ravi, R.

Date

Language

Embargo Status

N/A

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

We study the problem of locating facilities on the nodes of a network to maximize the expected demand serviced. The edges of the input graph are subject to random failure due to a disruptive event. We consider a special type of failure correlation. The edge dependency model assumes that the failure of a more reliable edge implies the failure of all less reliable ones. Under this dependency model called Linear Reliability Order (LRO) we give two polynomial time exact algorithms. When two distinct LRO's exist, we prove the total unimodularity of a linear programming formulation. In addition, we show that minimizing the sum of facility opening costs and expected cost of unserviced demand under two orderings reduces to a matching problem. We prove NP-hardness of the three orderings case and show that the problem with an arbitrary number of orderings generalizes the deterministic maximum coverage problem. When a demand point can be covered only if a facility exists within a distance limit, we show that the problem is NP-hard even for a single ordering.

Source

Publisher

Springer New York LLC

Citation

item.page.haspartof

Source

Journal of Combinatorial Optimization

item.page.ispartofseries

item.page.edition

DOI

10.1007/s10878-017-0121-5

item.page.datauri

item.page.link

Rights

N/A

Copyrights Note

Rights and licensing

N/A

Endorsement

Review

Supplemented By

Referenced By

Related Patent

Related Goal

Item type:Goal, Access status: Open Access ,
03 - Good Health and Well-being
Over the last 15 years, the number of childhood deaths has been cut in half. This proves that it is possible to win the fight against almost every disease. Still, we are spending an astonishing amount of money and resources on treating illnesses that are surprisingly easy to prevent. The new goal for worldwide Good Health promotes healthy lifestyles, preventive measures and modern, efficient healthcare for everyone.
Item type:Goal, Access status: Open Access ,
16 - Peace, Justice and Strong Institutions
Compassion and a strong moral compass is essential to every democratic society.Yet, persecution, injustice and abuse still runs rampant and is tearing at the very fabric of civilization. We must ensure that we have strong institutions, global standards of justice, and a commitment to peace everywhere.
Google Scholar
Scholar'da Ara ↗
Altmetric
Dimensions
PlumX Metrikleri
BIP! Indicators