How to Allocate Network Centers

DOI10.1006/jagm.1993.1047zbMath0784.68012OpenAlexW1971680805WikidataQ57968168 ScholiaQ57968168MaRDI QIDQ4275335

Judit Bar-Ilan, Guy Kortsarz, David Peleg

Publication date: 22 March 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/67bc5054613d69b34f41d1654694b3970e6ca7d9

zbMATH Keywords

approximation algorithms communication network distributed network $NP$-hard allocating and utilizing centers balanced versions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Related Items (49)

New approximation results for resource replication problems ⋮ The load-distance balancing problem ⋮ Distributed distance domination in graphs with no $K_{2,t}$-minor ⋮ Parameterized Complexity for Domination Problems on Degenerate Graphs ⋮ Capacitated $p$-center problem with failure foresight ⋮ Optimal broadcast domination in polynomial time ⋮ When centers can fail: a close second opportunity ⋮ Distributed approximation of capacitated dominating sets ⋮ Compact location problems ⋮ Approximability results for the $p$-centdian and the converse centdian problems ⋮ Capacitated covering problems in geometric spaces ⋮ Structural parameters, tight bounds, and approximation for $(k, r)$-center ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Centrality of trees for capacitated $k$-center ⋮ Improved bounds for metric capacitated covering problems ⋮ Approximability results for the converse connectedp-centre problem^† ⋮ Massively parallel and streaming algorithms for balanced clustering ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Tight FPT approximation for constrained $k$-center and $k$-supplier ⋮ Graph clustering ⋮ $k$-balanced center location problem: a new multi-objective facility location problem ⋮ Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ The fault-tolerant capacitated $K$-center problem ⋮ A model for minimizing active processor time ⋮ On the cost of essentially fair clusterings ⋮ ALGORITHMS FOR MINIMUM CONNECTED CAPACITATED DOMINATING SET PROBLEM ⋮ Improved approximation algorithms for capacitated fault-tolerant $k$-center ⋮ Randomized approximation of bounded multicovering problems ⋮ Faster balanced clusterings in high dimension ⋮ $k$-center problems with minimum coverage ⋮ An exact algorithm for the capacitated vertex $p$-center problem ⋮ Facility location with dynamic distance functions ⋮ Minimax models for capacitated $p$-center problem in uncertain environment ⋮ Statistical mechanics of the directed 2-distance minimal dominating set problem ⋮ An adaptive probabilistic algorithm for online $k$-center clustering ⋮ The capacitated single-source p-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints ⋮ A distributed algorithm to find $k$-dominating sets ⋮ Large-scale local search heuristics for the capacitated vertexp-center problem ⋮ Fault tolerant $K$-center problems ⋮ Lagrangean duals and exact solution to the capacitated $p$-center problem ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Generalized submodular cover problems and applications ⋮ On capacitated covering with unit balls ⋮ A constant-factor approximation algorithm for the $k$-median problem

This page was built for publication: How to Allocate Network Centers