An Algorithmic Approach to Network Location Problems. I: Thep-Centers

DOI10.1137/0137040zbMath0432.90074OpenAlexW4239852074WikidataQ59760353 ScholiaQ59760353MaRDI QIDQ3870690

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/0137040

zbMATH Keywords

tree computational complexity graph NP-complete problems polynomial algorithm dominating set centers network location centroid medians diameter of graph servicing min-max criterion location of service station p-centers 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

Efficient algorithms for the round-trip 1-center and 1-median problems, Exact algorithms for handling outliers in center location problems on networks using $k$-max 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, Bounded fan-out $m$-center problem, The $p$-neighbor $k$-center problem, Finding a longest nonnegative path in a constant degree tree, An efficient algorithm for the length-constrained heaviest path problem on a tree, The mixed center location problem, A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, Kinetic clustering of points on the line, Inverse eccentric vertex problem on networks, A scalable exact algorithm for the vertex $p$-center problem, The linking set problem: a polynomial special case of the multiple-choice knapsack problem, Finding the $\ell$-core of a tree, A heuristic for the p-center problem in graphs, Capacitated $p$-center problem with failure foresight, The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance, Continuous multifacility ordered median location problems, Maximum weight independent set in trees, Robust vertex $p$-center model for locating urgent relief distribution centers, Double bound method for solving the $p$-center location problem, Improving the quality of heuristic solutions for the capacitated vertex $p$-center problem through iterated greedy local search with variable neighborhood descent, When centers can fail: a close second opportunity, Representation of the non-dominated set in biobjective discrete optimization, An $O(mn)$ algorithm for the anti-cent-dian problem, An improved algorithm for the $p$-center problem on interval graphs with unit lengths, Location and layout planning. A survey, An improved algorithm for the minmax regret path centdian problem on trees, The biobjective absolute center problem, The algorithmic use of hypertree structure and maximum neighbourhood orderings, An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs, The multi-service center problem, Designing humanitarian supply chains by incorporating actual post-disaster decisions, Bounded-degree minimum-radius spanning trees in wireless sensor networks, A double annealing algorithm for discrete location/allocation problems, The probabilistic $p$-center problem: planning service for potential customers, Two paths location of a tree with positive or negative weights, The connected $p$-center problem on block graphs with forbidden vertices, NP-completeness of some type of p-center problem, Progressive scattered data filtering., The absolute center of a unicyclic network, Backup 2-center on interval graphs, The discrete p-dispersion problem, Algorithms for the m-center problems: A survey, The distance-domination numbers of trees, Synthetic optimization model and algorithm for railway freight center station location and wagon flow organization problem, Sorting weighted distances with applications to objective function evaluations in single facility location problems., On search over rationals, On locating new facilities in a competitive environment, Locational analysis, The inverse 1-center problem on cycles with variable edge lengths, An algorithm to evaluate public transportation stops for minimizing passenger walking distance, An algorithm for finding the absolute center of a network, The maximin gradual cover location problem, Location routing problems on trees, Algorithms for the minimum diameter terminal Steiner tree problem, Total distance, Wiener index and opportunity index in wreath products of star graphs, Inverse $k$-centrum problem on trees with variable vertex weights, On the minimum diameter spanning tree problem, Efficient algorithms for the one-dimensional $k$-center problem, Computing the clique-width of cactus graphs, Sequential location of two facilities: comparing random to optimal location of the first facility, An optimal algorithm for the weighted backup 2-center problem on a tree, Algorithm to find a maximum 2-packing set in a cactus, Combinatorial network abstraction by trees and distances, The 2-radius and 2-radiian problems on trees, A reactive GRASP for a commercial territory design problem with multiple balancing requirements, New relaxation-based algorithms for the optimal solution of the continuous and discrete $p$-center problems, On worst-case aggregation analysis for network location problems, Network location of a reliable center using the most reliable route policy, The minimum weight $t$-composition of an integer, Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms, Star $p$-hub center problem and star $p$-hub median problem with bounded path lengths, Modelling gateway placement in wireless networks: geometric $k$-centres of unit disc graphs, Orthogonal segment stabbing, Approximation algorithm for the kinetic robust $k$-center problem, Location analysis: a synthesis and survey, Group centre and group median of a tree, Efficient parallel algorithms for r-dominating set and p-center problems on trees, Locating an absolute center on graphs that are almost trees, Dominant, an algorithm for the $p$-center problem., On weighted rectilinear 2-center and 3-center problems, Approximate maxima finding of continuous functions under restricted budget, Aggregation error for location models: Survey and analysis, A simple heuristic for the p-centre problem, Kinetic maintenance of mobile $k$-centres on trees, Improved complexity results for several multifacility location problems on trees, Generalized $p$-center problems: Complexity results and approximation algorithms, Improved approximability and non-approximability results for graph diameter decreasing problems, Algorithms for the robust 1-center problem on a tree, Vertex fusion under distance constraints, Some new algorithms for location problems on networks, The absolute centre of a graph, Combinatorial analysis (nonnegative matrices, algorithmic problems), 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, The least element property of center location on tree networks with applications to distance and precedence constrained problems, Enhancements to two exact algorithms for solving the vertex $P$-center problem, Demand point aggregation for planar covering location models, Approximability results for the $p$-centdian and the converse centdian problems, Mean-variance value at risk criterion for solving a $p$-median location problem on networks with type-2 intuitionistic fuzzy weights, The Minmax Regret Reverse 1-Median Problem on Trees with Uncertain Vertex Weights, Min-Max-Min Optimization with Smooth and Strongly Convex Objectives, On fixed-parameter solvability of the minimax path location problem, The multifacility center problems with random demand weights, A vertex weighting-based double-tabu search algorithm for the classical $p$-center problem, Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS, The extensive 1-median problem with radius on networks, A capacitated biobjective location problem with uniformly distributed demands in the UAV‐supported delivery operation, The max-sum inverse median location problem on trees with budget constraint, Location Science in Canada, Dynamically second-preferred $p$-center problem, Minmax centered $k$-partitioning of trees and applications to sink evacuation with dynamic confluent flows, The uniform cost reverse 1-centdian location problem on tree networks with edge length reduction, Variable neighborhood search: the power of change and simplicity, Exact solution approaches for the discrete α‐neighbor p‐center problem, Computing the center of uncertain points on cactus graphs, The Impact of Cooperation in Bilateral Network Creation, Locating Facilities on a Network to Minimize Their Average Service Radius, The algorithmic use of hypertree structure and maximum neighbourhood orderings, The $k$-centrum multi-facility location problem, Reload cost problems: Minimum diameter spanning tree, A linear-time algorithm for radius-optimally augmenting paths in a metric space, Delay-constrained minimum shortest path trees and related problems, Covering uncertain points in a tree, Comments on: ``Static and dynamic source locations in undirected networks, Continuous Center Problems, Discrete Center Problems, Exploiting Structure: Location Problems on Trees and Treelike Graphs, An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees, The connected p-median problem on complete multi-layered graphs, Solving the absolute 1-center problem in the quickest path case, The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, Computing a $(1+\varepsilon)$-approximate geometric minimum-diameter spanning tree, Continuous Facility Location on Graphs, Efficient algorithms for center problems in cactus networks, Efficient algorithms for the minmax regret path center problem with length constraint on trees, Asymmetric $k$-center with minimum coverage, Unreliable point facility location problems on networks, A finite algorithm for the continuousp-center location problem on a graph, A bibliography for some fundamental problem categories in discrete location science, Locating a semi-obnoxious facility with expropriation, Best location of service centers in a treelike network under budget constraints, Solving two location models with few facilities by using a hybrid heuristic: a real health resources case, The polygon burning problem, Location of Emergency Facilities with Uncertainty in the Demands, Approximating the Restricted 1-Center in Graphs, A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs, Locations on time-varying networks, Inverse stable point problem on trees under an extension of Chebyshev norm and Bottleneck Hamming distance, Novel Formulations and Logic-Based Benders Decomposition for the Integrated Parallel Machine Scheduling and Location Problem, A local analysis to determine all optimal solutions of $p$-$k$-$\max$ location problems on networks, On alternativep-center problems, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, Two Paths Location of a Tree with Positive or Negative Weights, A Survey on Approximation Mechanism Design Without Money for Facility Games, INDUCTIVE ALGORITHMS ON FINITE TREES, The multi-period $p$-center problem with time-dependent travel times, General network design: a unified view of combined location and network design problems, Simultaneous location-allocation of facilities and servers. a generalized heuristic, A linear time algorithm for connected $p$-centdian problem on block graphs, Optimizing the changing locations of mobile parcel lockers in last-mile distribution, A scaleable projection-based branch-and-cut algorithm for the $p$-center problem, A Class of Balanced Matrices Arising from Location Problems, Approximating the asymmetric $p$-center problem in parameterized complete digraphs, Stateless Information Dissemination Algorithms, Towards a machine learning-aided metaheuristic framework for a production/distribution system design problem, A linear time algorithm for balance vertices on trees, New approaches to the robust 1-center location problems on tree networks, Vertex fusion under diameter constraints, NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes, Constant work-space algorithms for facility location problems, On the complexity of some problems of searching for a family of disjoint clusters, An improved algorithm for the minmax regret path center problem on trees, Optimization problems with unimodal functions in max-separabal constraints, A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives, Facility location for large-scale emergencies, Computational aspects of the inverse single facility location problem on trees under $l_k$-norm, $k$-means genetic algorithms with greedy genetic operators, On some inverse 1-center location problems, The complete vertex $p$-center problem, The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy, Kinetic Maintenance of Mobile k-Centres on Trees, Applications of the DM‐GRASP heuristic: a survey, A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler, Unnamed Item, The obnoxious facilities planar $p$-median problem, A two-stage robust model for a reliable $p$-center facility location problem, Confined location of facilities on a graph, The stratified $p$-center problem, A dual bounding scheme for a territory design problem, Un nuevo resultado sobre la complejidad del problema delP-centro, An exact algorithm for the capacitated vertex $p$-center problem, The backup 2‐center and backup 2‐median problems on trees, Facility location with dynamic distance functions, Asymmetry in $k$-center variants, Minimax flow tree problems, The β-reliable minimax and maximin location problems on a network with probabilistic weights, Reverse 1-center problem on weighted trees, Solving thep-Center problem with Tabu Search and Variable Neighborhood Search, Inverse group 1-median problem on trees, Minimum diameter vertex-weighted Steiner tree, Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability, Solving multiple facilities location problems with separated clusters, Mathematical Models and Search Algorithms for the Capacitated p-Center Problem, An algorithm for solving the bi-objective median path-shaped facility on a tree network, A historical perspective on location problems, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, The capacitated single-source p-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique, Partitioning trees: Matching, domination, and maximum diameter, Employing Sink Mobility to Extend the Lifetime of Wireless Sensor Networks, Large-scale local search heuristics for the capacitated vertexp-center problem, The weighted $k$-center problem in trees for fixed $k$, A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location, A linear algorithm for the domination number of a series-parallel graph, Improving fairness in ambulance planning by time sharing, A combinatorial algorithm for the ordered 1-median problem on cactus graphs, Intersections and circuits in sets of line segments, An O(n log n)-Time Algorithm for the k-Center Problem in Trees, Combinatorial algorithms for the uniform-cost inverse 1-center problem on weighted trees, Unnamed Item, A polynomial algorithm for the two-connections variant of the tree $p$-median problem, Polynomially bounded algorithms for locatingp-centers on a tree, Exploiting flat subspaces in local search for $p$-center problem and two fault-tolerant variants, Broadcasting in Trees with Multiple Originators, Unnamed Item, On the minmax regret path median problem on trees, Center problems with pos/neg weights on trees, Robust weighted vertex $p$-center model considering uncertain data: an application to emergency management, Continuous facility location on graphs, An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree