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

DOI10.1007/S00453-020-00693-8zbMATH Open1453.68213OpenAlexW3012505214MaRDI QIDQ2196606FDOQ2196606

Authors Refael Hassin, R. Ravi, F. Sibel Salman, Danny Segev

Publication date 3 September 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-020-00693-8

zbMATH Keywords

dynamic programmingfacility locationFPTAShardnessrandom arc failures

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Multiple facility location on a network with linear reliability order of edges
• Reliability problems in multiple path-shaped facility location on networks
• Unreliable point facility location problems on networks
• The reliable facility location problem: formulations, heuristics, and approximation algorithms
• Facility location on planar graphs with unreliable links

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1063797 (Why is no real title available?)
• scientific article; zbMATH DE number 3256625 (Why is no real title available?)
• A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
• A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges
• A single facility location problem on a tree with unreliable edges
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Computational Complexity of Network Reliability Analysis: An Overview
• Locating A Broadcast Facility In An Unreliable Network
• Location of facilities on a network subject to a single‐edge failure
• Multiple facility location on a network with linear reliability order of edges
• Network location of a reliable center using the most reliable route policy
• Optimal location of facilities on a network with an unreliable node or link
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Probability Inequalities for Sums of Bounded Random Variables
• Reducibility among combinatorial problems
• Some APX-completeness results for cubic graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems

Cited in

(4)

• Facility location on planar graphs with unreliable links
• Multiple facility location on a network with linear reliability order of edges
• On the parameterized complexity of the expected coverage problem
• Reliability problems in multiple path-shaped facility location on networks

This page was built for publication: The approximability of multiple facility location on directed networks with random arc failures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196606)