An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs

DOI10.1016/0167-6377(96)00021-1zbMath0865.90089OpenAlexW2090879820MaRDI QIDQ2564302

Publication date: 7 January 1997

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(96)00021-1

zbMATH Keywords

facility location complexity bound tree graphs \(p\)-median problems \(p\)-coverage problems \(p\)-median problem on trees

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Dynamic programming (90C39) Discrete location and assignment (90B80)

Related Items

A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint, A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, Efficient algorithms for centers and medians in interval and circular-arc graphs, Improved algorithms for some competitive location centroid problems on paths, trees and graphs, DIAMETER-CONSTRAINED STEINER TREES, Finding the \(\ell\)-core of a tree, The connected \(p\)-median problem on block graphs, Improved algorithms for joint optimization of facility locations and network connections, The web proxy location problem in general tree of rings networks, The general facility location problem with connectivity on trees, Algorithms for central-median paths with bounded length on trees, Extensive facility location problems on networks: an updated review, An improved algorithm for the minmax regret path centdian problem on trees, Median problems with positive and negative weights on cycles and cacti, Revisiting \(k\)-sum optimization, Polyhedral properties of the \(K\)-median problem on a tree, Two Paths Location of a Tree with Positive or Negative Weights, The multi-service center problem, The most probable allocation solution for the p-median problem, \(k\)-median: exact recovery in the extended stochastic ball model, Mean-variance value at risk criterion for solving a \(p\)-median location problem on networks with type-2 intuitionistic fuzzy weights, The backup 2-median problem on block graphs, Finding a core of a tree with pos/neg weight, Efficient algorithms for finding <scp>2‐medians</scp> of a tree, The extensive 1-median problem with radius on networks, Two paths location of a tree with positive or negative weights, Improved algorithms for computing minmax regret sinks on dynamic path and tree networks, An improved algorithm for the minmax regret path center problem on trees, The balanced 2-median and 2-maxian problems on a tree, Optimizing server placement in distributed systems in the presence of competition, Minimum diameter cost-constrained Steiner trees, Unnamed Item, Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Locating Facilities on a Network to Minimize Their Average Service Radius, Maintaining centdians in a fully dynamic forest with top trees, A \(k\)-product uncapacitated facility location problem, Finding an optimal core on a tree network with M/G/c/c state-dependent queues, Median problems on wheels and cactus graphs, A linear time algorithm for computing minmax regret 1-median on a tree network, Finding the conditional location of a median path on a tree, Location routing problems on trees, Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks, The \(p\)-median polytope of \(Y\)-free graphs: An application of the matching theory, The \(p\)-maxian problem on a tree, Classical and inverse median location problems under uncertain environment, On the \(p\)-median polytope of \(Y\)-free graphs, Inverse \(p\)-median problems with variable edge lengths, The \(k\)-centrum multi-facility location problem, A large class of facets for the \(K\)-median polytope, Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees, An \(O(n(\log n)^{2}/\log \log n)\) algorithm for the single maximum coverage location or the \((1,X_p)\)-medianoid problem on trees, Locating tree-shaped facilities using the ordered median objective, The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers, An optimal algorithm for the maximum-density path in a tree, 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, Efficient computation of 2-medians in a tree network with positive/negative weights, Joint object placement and node dimensioning for internet content distribution, Improved complexity results for several multifacility location problems on trees, Minimax regret path location on trees, Optimal algorithms for selective variants of the classical and inverse median location problems on trees, A combinatorial algorithm for the ordered 1-median problem on cactus graphs, 2-medians in trees with pos/neg weights, The traveling \(k\)-median problem: approximating optimal network coverage, One-way and round-trip center location problems, Weighted cache location problem with identical servers, Reliability problems in multiple path-shaped facility location on networks, A polynomial algorithm for the two-connections variant of the tree \(p\)-median problem, On the minmax regret path median problem on trees, On the exponential cardinality of FDS for the ordered \(p\)-median problem, A constant-factor approximation algorithm for the \(k\)-median problem, The minimum \(k\)-storage problem on directed graphs

Cites Work