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
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
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)
Cites Work
- A threshold of ln n for approximating set cover
- Probability Inequalities for Sums of Bounded Random Variables
- Title not available (Why is that?)
- 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
- An analysis of approximations for maximizing submodular set functions—I
- Computational Complexity of Network Reliability Analysis: An Overview
- Optimal location of facilities on a network with an unreliable node or link
- Location of facilities on a network subject to a single‐edge failure
- A single facility location problem on a tree with unreliable edges
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Title not available (Why is that?)
- A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges
- Title not available (Why is that?)
- Locating A Broadcast Facility In An Unreliable Network
- A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
- Network location of a reliable center using the most reliable route policy
- Multiple facility location on a network with linear reliability order of edges
Cited In (3)
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)
