Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier

DOI10.1016/j.tcs.2022.11.001OpenAlexW3210396596MaRDI QIDQ2699973

Dishant Goyal, Ragesh Jaiswal

Publication date: 20 April 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

clusteringapproximation algorithmsfixed-parameter tractability\(k\)-center\(k\)-supplier

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

A parameterized approximation algorithm for the multiple allocation \(k\)-hub center ⋮ An approximation algorithm for diversity-aware fair \(k\)-supplier problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Strong computational lower bounds via parameterized complexity
• Centrality of trees for capacitated \(k\)-center
• Clustering to minimize the maximum intercluster distance
• A strongly polynomial minimum cost circulation algorithm
• Fault tolerant \(K\)-center problems
• A survey of healthcare facility location
• Faster algorithms for the constrained \(k\)-means problem
• Fault tolerant clustering with outliers
• A unified framework for clustering constrained data without locality property
• Capacitated center problems with two-sided bounds and outliers
• Achieving anonymity via clustering
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Constant Factor Approximation for Capacitated k-Center with Outliers
• Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
• Clustering with Diversity
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• How to Allocate Network Centers
• The Capacitated K-Center Problem
• Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• On the approximability of the maximum common subgraph problem
• On the Parameterized Complexity of Approximating Dominating Set
• Database Theory - ICDT 2005
• Parameterized Algorithms
• On the cost of essentially fair clusterings
• The Non-Uniform k -Center Problem
• A unified framework of FPT approximation algorithms for clustering problems
• FPT Approximation for Constrained Metric k-Median/Means

This page was built for publication: Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier