Locating tree-shaped facilities using the ordered median objective

DOI10.1007/s10107-004-0547-2zbMath1079.90081WikidataQ58217294 ScholiaQ58217294MaRDI QIDQ1771313

Arie Tamir, Justo Puerto

Publication date: 19 April 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-004-0547-2

zbMATH Keywords

linear programming; dynamic programming; tree network

Mathematics Subject Classification ID

90C90: Applications of mathematical programming

90B80: Discrete location and assignment

Related Items

The continuous and discrete path‐variance problems on trees, Tight bounds from a path based formulation for the tree of hub location problem, Finding the conditional location of a median path on a tree, Center location problems on tree graphs with subtree-shaped customers, Extensive facility location problems on networks with equity measures, The tree of hubs location problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• Finding the two-core of a tree
• Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem
• A review of extensive facility location in networks
• Minimizing symmetric submodular functions
• A unifying location model on tree graphs based on submodularity property
• Sorting weighted distances with applications to objective function evaluations in single facility location problems.
• The centdian subtree on tree networks
• Minimizing the sum of the \(k\) largest functions in linear time.
• Algorithmic results for ordered median problems
• A flexible approach to location problems
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Finding a 2-Core of a Tree in Linear Time
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• On locating path- or tree-shaped facilities on networks
• Algorithms for a Core and k-Tree Core of a Tree
• On finding the core of a tree with a specified length
• The optimal location of a path or tree in a tree network
• A linear algorithm for a core of a tree
• The generalized P‐forest problem on a tree network
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
• A Depth-First Dynamic Programming Algorithm for the Tree Knapsack Problem
• Aggregation Error Bounds for a Class of Location Models
• Worst-case incremental analysis for a class ofp-facility location problems
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Multifacility ordered median problems on networks: A further analysis
• Efficient algorithms for finding the (k,l)-core of tree networks
• Efficient Algorithms for Finding a Core of a Tree with a Specified Length
• Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
• The \(k\)-centrum multi-facility location problem