Easy and hard bottleneck location problems

DOI10.1016/0166-218X(79)90044-1zbMATH Open0424.90049OpenAlexW1983197449MaRDI QIDQ1135201FDOQ1135201

Authors: S. H. Smith 

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

zbMATH Keywords

dynamic programmingdualityNP-complete problempolynomial time algorithmbinary searchNP-hard problemblocking cluttersbottleneck location problem on a graphdisconnecting sets on a graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Bottleneck extrema
• P-Complete Approximation Problems
• Title not available (Why is that?)
• Scheduling to Minimize Interaction Cost

Cited In (61)

• Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
• Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
• Generalized center problems with outliers
• The ordered \(k\)-median problem: surrogate models and approximation algorithms
• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• A constant approximation for colorful \(k\)-center
• Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• Fair colorful \(k\)-center clustering
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• Fair colorful \(k\)-center clustering
• Location of rectilinear center trajectories
• Approximability results for the $p$-centdian and the converse centdian problems
• Obstructions to a small hyperbolicity in Helly graphs
• A new compact formulation for the discrete \(p\)-dispersion problem
• Special issue on Locational analysis
• A simple heuristic for the p-centre problem
• Graph theory (algorithmic, algebraic, and metric problems)
• The fault-tolerant capacitated \(K\)-center problem
• Kinetic clustering of points on the line
• Approximability results for the converse connected \(p\)-centre problem
• On the cost of essentially fair clusterings
• Approximation algorithms for clustering with dynamic points
• Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• Title not available (Why is that?)
• Fault tolerant \(K\)-center problems
• A heuristic for the p-center problem in graphs
• \(k\)-center problems with minimum coverage
• Recent developments in approximation algorithms for facility location and clustering problems
• Facility location with dynamic distance functions
• Analytical models for locating undesirable facilities
• Generalized center problems with outliers
• A lottery model for center-type problems with outliers
• On clustering with discounts
• Asymmetric \(k\)-center with minimum coverage
• Insertion heuristics for central cycle problems
• Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs
• On worst-case aggregation analysis for network location problems
• Locational analysis
• A Lottery Model for Center-Type Problems With Outliers
• Graph clustering
• Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints
• On interval and circular-arc covering problems
• The weighted \(k\)-center problem in trees for fixed \(k\)
• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• Title not available (Why is that?)
• Privacy preserving clustering with constraints
• Reverse greedy is bad for \(k\)-center
• Stateless Information Dissemination Algorithms
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• An adaptive probabilistic algorithm for online \(k\)-center clustering
• Client assignment problems for latency minimization
• Small Space Stream Summary for Matroid Center
• Improved separated red-blue center clustering
• Approximating the probabilistic \(p\)-center problem under pressure
• Connected \(k\)-center and \(k\)-diameter clustering
• Clustering with faulty centers
• The distributed algorithms for the lower-bounded \(k\)-center clustering in metric space
• New algorithms for fair \(k\)-center problem with outliers and capacity constraints
• Mind the gap: edge facility location problems in theory and practice

This page was built for publication: Easy and hard bottleneck location problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1135201)