A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

DOI10.1007/s10878-017-0213-2zbMath1412.90130OpenAlexW2769085521WikidataQ62043089 ScholiaQ62043089MaRDI QIDQ1631680

Wei Ding, Ke Qiu

Publication date: 6 December 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0213-2

zbMATH Keywords

treeedge-splittingquadratic timecontinuous connected 2-facility

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• A linear time algorithm for computing minmax regret 1-median on a tree network
• Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks
• An optimal algorithm for the weighted backup 2-center problem on a tree
• A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
• Algorithms for central-median paths with bounded length on trees
• Polyhedral properties of the \(K\)-median problem on a tree
• An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
• A note on the minmax regret centdian location on trees
• Center location problems on tree graphs with subtree-shaped customers
• Efficient algorithms for two generalized 2-median problems and the group median problem on trees
• A polynomial method for the pos/neg weighted 3-median problem on a tree
• Approximation algorithms for connected facility location problems
• Optimal algorithms for the path/tree-shaped facility location problems in trees
• Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem
• A unifying location model on tree graphs based on submodularity property
• The least element property of center location on tree networks with applications to distance and precedence constrained problems
• Robust discrete optimization and its applications
• Algorithms for the robust 1-center problem on a tree
• 2-medians in trees with pos/neg weights
• The centdian subtree on tree networks
• On the 2-MRS problem in a tree with unreliable edges
• Center problems with pos/neg weights on trees
• A note on the robust 1-center problem on trees
• Primal-dual algorithms for connected facility location problems
• Connected facility location via random facility sampling and core detouring
• On the minmax regret path median problem on trees
• Improved algorithms for some competitive location centroid problems on paths, trees and graphs
• The \(p\)-maxian problem on a tree
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Robust location problems with pos/neg weights on a tree
• The Obnoxious Center Problem on a Tree
• Dual-Based Local Search for the Connected Facility Location and Related Problems
• Minimax regret path location on trees
• On locating path- or tree-shaped facilities on networks
• Proof verification and the hardness of approximation problems
• Approximation Algorithms for Problems Combining Facility Location and Network Design
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
• Simpler and better approximation algorithms for network design
• New Results on the Complexity of p-Centre Problems
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• The optimal location of a path or tree in a tree network
• The minimax multistop location problem on a tree
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• A linear algorithm for a core of a tree
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Polynomially bounded algorithms for locatingp-centers on a tree
• An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree
• Locating Centers on a Tree with Discontinuous Supply and Demand Regions
• Obnoxious Facility Location on Graphs
• Distance-constrained multifacility minimax location problems on tree networks
• The generalized P‐forest problem on a tree network
• Minimax regret p-center location on a network with demand uncertainty
• Minmax-regret robust 1-median location on a tree
• Minmax Regret Median Location on a Network Under Uncertainty
• A polynomial algorithm for thep-centdian problem on a tree
• Finding kth paths and p-centers by generating and searching good data structures
• An improved algorithm for the minmax regret median problem on a tree
• An improved algorithm for the distance constrainedp-center location problem with mutual communication on tree networks
• A single facility location problem on a tree with unreliable edges
• Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
• Improved algorithms for the minmax-regret 1-center and 1-median problems
• Provisioning a virtual private network
• Collection depots facility location problems in trees
• An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The $p$-Center Problem in Tree Networks Revisited
• Mathematical Foundations of Computer Science 2003
• Conditional location of path and tree shaped facilities on trees
• The bi‐criteria doubly weighted center‐median path problem on a tree
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• A Branch and Cut Algorithm for a Steiner Tree-Star Problem
• The \(k\)-centrum multi-facility location problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A quadratic time exact algorithm for continuous connected 2-facility location problem in trees