An Algorithmic Approach to Network Location Problems. II: Thep-Medians

DOI10.1137/0137041zbMath0432.90075OpenAlexW1984953641MaRDI QIDQ3870691

Publication date: 1979

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0137041

zbMATH Keywords

tree computational complexity median network location NP-hard problem centroid NP-complete problem algorithmic approach p-center servicing radius of a graph p-medians location of service stations optimal location center unweighted planar graphs w-centroid

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Queues and service in operations research (90B22) Applications of graph theory to circuits and networks (94C15)

Related Items

Principal points analysis via p-median problem for binary data, Efficient algorithms for centers and medians in interval and circular-arc graphs, Computing the Center of Uncertain Points on Tree Networks, An efficient algorithm for solving the median problem on real road networks, Unreliable point facility location problems on networks, Locations on time-varying networks, Inverse stable point problem on trees under an extension of Chebyshev norm and Bottleneck Hamming distance, Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space, On the Tree Conjecture for the Network Creation Game, Two Paths Location of a Tree with Positive or Negative Weights, A Survey on Approximation Mechanism Design Without Money for Facility Games, A linear time algorithm for connected $p$-centdian problem on block graphs, A centroid labelling technique and its application to path selection in trees, The most probable allocation solution for the p-median problem, Discrete facility location in machine learning, $k$-median: exact recovery in the extended stochastic ball model, Approximability results for the $p$-centdian and the converse centdian problems, Proximity, remoteness and maximum degree in graphs, The Minmax Regret Reverse 1-Median Problem on Trees with Uncertain Vertex Weights, On fixed-parameter solvability of the minimax path location problem, Efficient algorithms for finding <scp>2‐medians</scp> of a tree, The extensive 1-median problem with radius on networks, The max-sum inverse median location problem on trees with budget constraint, Location Science in Canada, A trajectory based heuristic for the planar $p$-median problem, w-Centroids and Least (w, l)-Central Subtrees in Weighted Trees, The Connected p-Center Problem on Cactus Graphs, The uniform cost reverse 1-centdian location problem on tree networks with edge length reduction, An efficient Benders decomposition for the $p$-median problem, The balanced 2-median and 2-maxian problems on a tree, On Metric Clustering to Minimize the Sum of Radii, Unnamed Item, On some inverse 1-center location problems, The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy, Locating Facilities on a Network to Minimize Their Average Service Radius, Optimal Control Strategies for Incoming Inspection, Unnamed Item, Placing resources in a tree: Dynamic and static algorithms, Ant colony optimization for finding medians of weighted graphs, The $k$-centrum multi-facility location problem, Probabilistic stopping rules for GRASP heuristics and extensions, Variable neighborhood search: Principles and applications, Unnamed Item, A family of facets for the uncapacitated $p$-median polytope, The backup 2‐center and backup 2‐median problems on trees, Reverse 1-center problem on weighted trees, Statuses and branch-weights of weighted trees, Pharmacy duty scheduling problem, A hybrid data mining metaheuristic for the p‐median problem, Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems, Covering uncertain points in a tree, Efficient computation of 2-medians in a tree network with positive/negative weights, Allocating servers to facilities, when demand is elastic to travel and waiting times, Optimal algorithms for selective variants of the classical and inverse median location problems on trees, The Maximum Coverage Location Problem, One-way and round-trip center location problems, Solving the $p$-median problem with pos/neg weights by variable neighborhood search and some results for special cases, Unnamed Item, The connected p-median problem on complete multi-layered graphs, Minimean Location of Different Facilities on a Line Network, Problems of discrete optimization: challenges and main approaches to solve them, The connected $p$-center problem on cactus graphs, Clustering to minimize the sum of cluster diameters, Efficient algorithms for the minmax regret path center problem with length constraint on trees, The $w$-centroids and least $w$-central subtrees in weighted trees, A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, A theory for memory-based learning, A modified $p$-median model for the emergency facilities location problem and its variable neighbourhood search-based algorithm, Finding the $\ell$-core of a tree, An extended covering model for flexible discrete and equity location problems, Making a state-of-the-art heuristic faster with data mining, The network $p$-median problem with discrete probabilistic demand weights, A bibliography for some fundamental problem categories in discrete location science, A neural model for the $p$-median problem, BEAMR: an exact and approximate model for the $p$-median problem, Trees with unique least central subtrees, A distance-limited continuous location-allocation problem for spatial planning of decentralized systems, A survey of healthcare facility location, A new approach to cooperative competition in facility location problems: mathematical formulations and an approximation algorithm, Minimum status of series-reduced trees with given parameters, An improved $(1+1)$ evolutionary algorithm for $k$-Median clustering problem with performance guarantee, Location and layout planning. A survey, Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints, An improved algorithm for the minmax regret path centdian problem on trees, A maximum $b$-matching problem arising from median location models with applications to the roommates problem, Some heuristic methods for solving $p$-median problems with a coverage constraint, Design and analysis of hybrid metaheuristics for the reliability $p$-median problem, An approximation algorithm for the $p$-hub median problem, A linear algorithm for the pos/neg-weighted 1-median problem on a cactus, The multi-service center problem, Minimum statuses of connected graphs with fixed maximum degree and order, Optimal algorithms for generalized searching in sorted matrices, A voltage drop limited decentralized electric power distribution network, A hybrid artificial bee colony algorithm for the $p$-median problem with positive/negative weights, On discrete preferences and coordination, Ordered $p$-median problems with neighbourhoods, A linear time algorithm for balance vertices on trees, Finding a core of a tree with pos/neg weight, Constant work-space algorithms for facility location problems, An improved algorithm for the minmax regret path center problem on trees, On the complexity of achieving proportional representation, A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives, Does Euclidean distance work well when the $p$-median model is applied in rural areas?, Computational aspects of the inverse single facility location problem on trees under $l_k$-norm, Budget constrained location problem with opening and closing of facilities., Step decision rules for multistage stochastic programming: a heuristic approach, Synthetic optimization model and algorithm for railway freight center station location and wagon flow organization problem, Approximability of the dispersed $\vec{p}$-neighbor $k$-supplier problem, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Product location, allocation and server home base location for an order picking line with multiple servers., Convex fuzzy $k$-medoids clustering, A minmax regret median problem on a tree under uncertain locations of the demand points, The inverse 1-center problem on cycles with variable edge lengths, 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, Location routing problems on trees, An ant colony algorithm for the pos/neg weighted $p$-median problem, The $p$-maxian problem on a tree, On the tree conjecture for the network creation game, Classical and inverse median location problems under uncertain environment, A mathematical model for fuzzy $p$-median problem with fuzzy weights and variables, The stochastic queue core problem, evacuation networks, and state-dependent queues, Location of facility based on simulated annealing and ``ZKW algorithms, A fast swap-based local search procedure for location problems, An adaptive multiphase approach for large unconditional and conditional $p$-median problems, A modified variable neighborhood search for the discrete ordered median problem, A computational study of a nonlinear minsum facility location problem, Lagrangean relaxation heuristics for the $p$-cable-trench problem, An aggregation heuristic for large scale p-median problem, A multi-product production/distribution system design problem with direct shipments and lateral transshipments, The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers, Location analysis: a synthesis and survey, Exact procedures for solving the discrete ordered median problem, Inverse group 1-median problem on trees, Minsum $k$-sink problem on path networks, Statuses and double branch weights of quadrangular outerplanar graphs, Solving multiple facilities location problems with separated clusters, Group centre and group median of a tree, Clustering and portfolio selection problems: a unified framework, The plant location problem with demand-dependent setup costs and centralized allocation, Near-optimal large-scale k-medoids clustering, A Lagrangian-based score for assessing the quality of pairwise constraints in semi-supervised clustering, Partial and perfect path covers of cographs, Some new algorithms for location problems on networks, An $O(pn^ 2)$ algorithm for the $p$-median and related problems on tree graphs, A combinatorial algorithm for the ordered 1-median problem on cactus graphs, Inverse 1-median problem on trees under mixed rectilinear and Chebyshev norms, On cutting planes for cardinality-constrained linear programs, 2-medians in trees with pos/neg weights, The traveling $k$-median problem: approximating optimal network coverage, Weighted cache location problem with identical servers, Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach, A polynomial algorithm for the two-connections variant of the tree $p$-median problem, Distance measure and the $p$-median problem in rural areas, An algorithm for finding a $k$-median in a directed tree, On the minmax regret path median problem on trees, A constant-factor approximation algorithm for the $k$-median problem, Problem-based optimal scenario generation and reduction in stochastic programming, Scenario reduction revisited: fundamental limits and guarantees, Efficient algorithms for the round-trip 1-center and 1-median problems, The inverse connected $p$-median problem on block graphs under various cost functions, Inverse 1-median problem on block graphs with variable vertex weights, A linear time algorithm for the $p$-maxian problem on trees with distance constraint, Finding the two-core of a tree, Orienting graphs to optimize reachability, A reliable budget-constrained FL/ND problem with unreliable facilities, Stop location design in public transportation networks: covering and accessibility objectives, The connected $p$-median problem on block graphs, The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance, The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Solving the $p$-median problem with a semi-Lagrangian relaxation, The general facility location problem with connectivity on trees, Variable neighborhood search for the pharmacy duty scheduling problem, Demand point aggregation method for covering problems with gradual coverage, $p$-median and $p$-dispersion problems: a bi-criteria analysis, The $p$-median problem: a survey of metaheuristic approaches, The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation, Algorithms for central-median paths with bounded length on trees, An $O(mn)$ algorithm for the anti-cent-dian problem, A genetic algorithm for the $p$-median problem with pos/neg weights, Computational study of large-scale $p$-median problems, Multiple voting location and single voting location on trees, A scatter search-based heuristic to locate capacitated transshipment points, Median problems with positive and negative weights on cycles and cacti, Meta-heuristic approaches with memory and evolution for a multi-product production/distribution system design problem, Incorporating waiting time in competitive location models, The leader-follower location model, Genetic algorithms for solving the discrete ordered median problem, The ordered capacitated facility location problem, The backup 2-median problem on block graphs, Prepositioning supplies in preparation for disasters, Two paths location of a tree with positive or negative weights, Bee colony optimization for the $p$-center problem, On the linear relaxation of the $p$-median problem, Optimizing server placement in distributed systems in the presence of competition, Complexity evaluation of benchmark instances for the $p$-median problem, The distance-domination numbers of trees, Comparative error bound theory for three location models: continuous demand versus discrete demand, The inverse 1-median problem on tree networks with variable real edge lengths, An O$(n\log n)$ version of the Averbakh-Berman algorithm for the robust median of a tree, On locating new facilities in a competitive environment, Comparing different metaheuristic approaches for the median path problem with bounded length, Locational analysis, Algorithms for location problems based on angular distances, Locating collection centers for incentive-dependent returns under a pick-up policy with capacitated vehicles, 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, Data aggregation for $p$-median problems, Total distance, Wiener index and opportunity index in wreath products of star graphs, Inverse $k$-centrum problem on trees with variable vertex weights, The location-dispatching problem: polyhedral results and content delivery network design, Dynamic and static algorithms for optimal placement of resources in a tree, The $p$-median polytope of $Y$-free graphs: An application of the matching theory, Threshold robustness in discrete facility location problems: a bi-objective approach, A fuzzy queuing location model with a genetic algorithm for congested systems, An effective heuristic for the $P$-median problem with application to ambulance location, On the $p$-median polytope of $Y$-free graphs, Sequential location of two facilities: comparing random to optimal location of the first facility, A parallelized lagrangean relaxation approach for the discrete ordered median problem, The 2-radius and 2-radiian problems on trees, The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers, Approximate solution of the $p$-median minimization problem, On worst-case aggregation analysis for network location problems, The multi-period incremental service facility location problem, Computing the center of uncertain points on tree networks, The heterogeneous $p$-median problem for categorization based clustering, Inverse $p$-median problems with variable edge lengths, Spiders are status unique in trees, A large class of facets for the $K$-median polytope, On metric clustering to minimize the sum of radii, The pos/neg-weighted median problem on block graphs with subgraph-shaped customers, Multiobjective optimization for multimode transportation problems, A continuous analysis framework for the solution of location-allocation problems with dense demand, 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, Confidence in heuristic solutions?, Approximation algorithms for minimum tree partition, Heuristic solution of the multisource Weber problem as a $p$-median problem, The continuous center set of a network, A computational evaluation of a general branch-and-price framework for capacitated network location problems, Optimal location with equitable loads, Up- and downgrading the 1-center in a network, A flexible model and efficient solution strategies for discrete location problems, Joint object placement and node dimensioning for internet content distribution, Improved complexity results for several multifacility location problems on trees, An efficient tabu search procedure for the $p$-median problem, Worst-case analysis of demand point aggregation for the Euclidean $p$-median problem, Distribution systems design with role dependent objectives, The absolute centre of a graph, Networks with Condorcet solutions, A comparison of two dual-based procedures for solving the p-median problem, Combinatorial analysis (nonnegative matrices, algorithmic problems), Models for planning capacity expansion in local access telecommunication networks, Network location problems with continuous link demands: p-medians on a chain and 2-medians on a tree, Bibliography on domination in graphs and some basic definitions of domination parameters, Efficient implementation of a shifting algorithm, The stochastic location-assignment problem on a tree, Heuristic procedures for solving the discrete ordered median problem