Improved approximation algorithms for capacitated fault-tolerant \(k\)-center

DOI10.1007/S00453-017-0398-XzbMath1408.68033OpenAlexW2770690069WikidataQ111288219 ScholiaQ111288219MaRDI QIDQ1742378

Lehilton L. C. Pedrosa, Samuel P. de Paula, Cristina G. Fernandes

Publication date: 11 April 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0398-x

zbMATH Keywords

linear programmingapproximation algorithmminimax problemfault toleranceLP roundingcapacitated \(k\)-center problemnon-uniform capacities

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Discrete location and assignment (90B80) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (3)

New algorithms for fair \(k\)-center problem with outliers and capacity constraints ⋮ \(k\)-balanced center location problem: a new multi-objective facility location problem ⋮ An adaptive probabilistic algorithm for online \(k\)-center clustering

Cites Work

• Unnamed Item
• Unnamed Item
• The \(p\)-neighbor \(k\)-center problem
• The fault-tolerant capacitated \(K\)-center problem
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Centrality of trees for capacitated \(k\)-center
• Clustering to minimize the maximum intercluster distance
• Easy and hard bottleneck location problems
• Fault tolerant \(K\)-center problems
• Constant Factor Approximation for Capacitated k-Center with Outliers
• A Best Possible Heuristic for the k-Center Problem
• How to Allocate Network Centers
• The Capacitated K-Center Problem
• Reducibility among Combinatorial Problems

This page was built for publication: Improved approximation algorithms for capacitated fault-tolerant \(k\)-center