Easy and hard bottleneck location problems
From MaRDI portal
Publication:1135201
DOI10.1016/0166-218X(79)90044-1zbMath0424.90049OpenAlexW1983197449MaRDI QIDQ1135201
Publication date: 1979
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(79)90044-1
dynamic programmingdualitypolynomial time algorithmNP-hard problemNP-complete problembinary searchblocking cluttersbottleneck location problem on a graphdisconnecting sets on a graph
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10)
Related Items (58)
A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Fair Colorful k-Center Clustering ⋮ Obstructions to a small hyperbolicity in Helly graphs ⋮ Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ Kinetic clustering of points on the line ⋮ Asymmetric \(k\)-center with minimum coverage ⋮ A heuristic for the p-center problem in graphs ⋮ Approximation algorithms for clustering with dynamic points ⋮ Analytical models for locating undesirable facilities ⋮ On clustering with discounts ⋮ Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs ⋮ Stateless Information Dissemination Algorithms ⋮ Approximability results for the $p$-centdian and the converse centdian problems ⋮ Clustering with faulty centers ⋮ Approximability results for the converse connectedp-centre problem† ⋮ Client assignment problems for latency minimization ⋮ New algorithms for fair \(k\)-center problem with outliers and capacity constraints ⋮ Mind the gap: edge facility location problems in theory and practice ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved separated red-blue center clustering ⋮ Graph clustering ⋮ Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem ⋮ Locational analysis ⋮ The fault-tolerant capacitated \(K\)-center problem ⋮ On the cost of essentially fair clusterings ⋮ Small Space Stream Summary for Matroid Center ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ A Lottery Model for Center-Type Problems with Outliers ⋮ Improved approximation algorithms for capacitated fault-tolerant \(k\)-center ⋮ A new compact formulation for the discrete \(p\)-dispersion problem ⋮ On worst-case aggregation analysis for network location problems ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Unnamed Item ⋮ \(k\)-center problems with minimum coverage ⋮ Facility location with dynamic distance functions ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Insertion heuristics for central cycle problems ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs ⋮ A Lottery Model for Center-Type Problems With Outliers ⋮ Generalized Center Problems with Outliers ⋮ Reverse greedy is bad for \(k\)-center ⋮ A simple heuristic for the p-centre problem ⋮ An adaptive probabilistic algorithm for online \(k\)-center clustering ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints ⋮ Special issue on Locational analysis ⋮ Location of rectilinear center trajectories ⋮ The weighted \(k\)-center problem in trees for fixed \(k\) ⋮ Fault tolerant \(K\)-center problems ⋮ On interval and circular-arc covering problems ⋮ Unnamed Item ⋮ Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Unnamed Item ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints ⋮ Fair colorful \(k\)-center clustering
Cites Work
This page was built for publication: Easy and hard bottleneck location problems
