The approximability of multiple facility location on directed networks with random arc failures
From MaRDI portal
Publication:2196606
DOI10.1007/s00453-020-00693-8zbMath1453.68213OpenAlexW3012505214MaRDI QIDQ2196606
R. Ravi, Danny Segev, F. Sibel Salman, Refael Hassin
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
Programming involving graphs or networks (90C35) Dynamic programming (90C39) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- 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
- A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges
- Optimal location of facilities on a network with an unreliable node or link
- Some APX-completeness results for cubic graphs
- Multiple facility location on a network with linear reliability order of edges
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- A threshold of ln n for approximating set cover
- Computational Complexity of Network Reliability Analysis: An Overview
- The Complexity of Enumeration and Reliability Problems
- Location of facilities on a network subject to a single‐edge failure
- An analysis of approximations for maximizing submodular set functions—I
- A single facility location problem on a tree with unreliable edges
- Reducibility among Combinatorial Problems
- Probability Inequalities for Sums of Bounded Random Variables
- Locating A Broadcast Facility In An Unreliable Network
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The approximability of multiple facility location on directed networks with random arc failures
