Centrality of trees for capacitated \(k\)-center

DOI10.1007/s10107-014-0857-yzbMath1337.90036arXiv1304.2983OpenAlexW2114589083MaRDI QIDQ896276

Shalmoli Gupta, Chandra Chekuri, Ola Svensson, Aditya Bhaskara, Vivek Madan, Hyung-Chan An

Publication date: 9 December 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.2983

zbMATH Keywords

approximation algorithmscapacitated \(k\)-center problemcapacitated network location problemsLP-rounding algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (20)

Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ Capacitated covering problems in geometric spaces ⋮ Improved bounds for metric capacitated covering problems ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ The Euclidean k-Supplier 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 ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Unnamed Item ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Improved approximation algorithms for capacitated fault-tolerant \(k\)-center ⋮ Faster balanced clusterings in high dimension ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ The capacitated single-source p-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique ⋮ Capacitated Covering Problems in Geometric Spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Clustering to minimize the maximum intercluster distance
• Improved approximation algorithms for capacitated facility location problems
• A constant-factor approximation algorithm for the \(k\)-median problem
• A 5-Approximation for Capacitated Facility Location
• The Design of Approximation Algorithms
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• A Best Possible Heuristic for the k-Center Problem
• Greedy Strikes Back: Improved Facility Location Algorithms
• How to Allocate Network Centers
• The Capacitated K-Center Problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• On Representatives of Subsets
• Improved Combinatorial Algorithms for Facility Location Problems
• Centrality of Trees for Capacitated k-Center
• Approximating k-median via pseudo-approximation
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• Integer Programming and Combinatorial Optimization
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

This page was built for publication: Centrality of trees for capacitated \(k\)-center