On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
DOI10.1134/S0081543821030081zbMath1470.90040OpenAlexW3185405485MaRDI QIDQ2043623
E. Kh. Gimadi, O. Yu. Tsidulko
Publication date: 3 August 2021
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s0081543821030081
treewidthpolynomial-time algorithmfacility location problemNP-hard problemmultiple allocationcapacitiessingle allocationpseudopolynomial-time algorithm
Programming involving graphs or networks (90C35) Trees (05C05) Deterministic network models in operations research (90B10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Cites Work
- Static and dynamic source locations in undirected networks
- Improved complexity bounds for location problems on the real line
- A partial k-arboretum of graphs with bounded treewidth
- On some optimization problems on \(k\)-trees and partial \(k\)-trees
- Submodular unsplittable flow on trees
- Locating Sources to Meet Flow Demands in Undirected Networks
- Simultaneous source location
- Treewidth: Characterizations, Applications, and Computations
- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- Graph minors. II. Algorithmic aspects of tree-width
- The concave least-weight subsequence problem revisited
- Location Science
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
