DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.72

On Tight FPT Time Approximation Algorithms for k-Clustering Problems

Authors: Han Dai, Shi Li, and Sijin Peng

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Following recent advances in combining approximation algorithms with fixed-parameter tractability (FPT), we study FPT-time approximation algorithms for minimum-norm k-clustering problems, parameterized by the number k of open facilities. For the capacitated setting, we give a tight (3+ε)-approximation for the general-norm capacitated k-clustering problem in FPT-time parameterized by k and ε. Prior to our work, such a result was only known for the capacitated k-median problem [Cohen-Addad and Li, 2019]. As a special case, our result yields an FPT-time 3-approximation for capacitated k-center. The problem has not been studied in the FPT-time setting, with the previous best known polynomial-time approximation ratio being 9 [An et al., 2015]. In the uncapacitated setting, we consider the top-cn norm k-clustering problem, where the goal of the problem is to minimize the top-cn norm of the connection distance vector. Our main result is a tight (1 + 2/(ec) + ε)-approximation algorithm for the problem with c ∈ (1/e, 1]. (For the case c ≤ 1/e, there is a simple tight (3+ε)-approximation.) Our framework can be easily extended to give a tight (3, 1 + 2/e + ε)-bi-criteria approximation for the (k-center, k-median) problem in FPT time, improving the previous best polynomial-time (4, 8) guarantee [Soroush Alamdari and David B. Shmoys, 2017]. All results are based on a unified framework: computing a (1+ε)-approximate solution using O((k log n)/ε) facilities S via LP rounding, sampling a few client representatives R based on the solution S, guessing a few pivots from S ∪ R and some radius information on the pivots, and solving the problem using the guesses. We believe this framework can lead to further results on k-clustering problems.

Cite as

Han Dai, Shi Li, and Sijin Peng. On Tight FPT Time Approximation Algorithms for k-Clustering Problems. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 72:1-72:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dai_et_al:LIPIcs.ICALP.2026.72,
  author =	{Dai, Han and Li, Shi and Peng, Sijin},
  title =	{{On Tight FPT Time Approximation Algorithms for k-Clustering Problems}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{72:1--72:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.72},
  URN =		{urn:nbn:de:0030-drops-264613},
  doi =		{10.4230/LIPIcs.ICALP.2026.72},
  annote =	{Keywords: Approximation algorithms, Monotone symmetric norms, Clustering, Fixed parameter tractability}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2025.26

Complexity of Local Search for CSPs Parameterized by Constraint Difference

Authors: Aditya Anand, Vincent Cohen-Addad, Tommaso D'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, and Sijin Peng

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract

In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset S of a universe U, the new input consists of a current solution P (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution S^*, the goal is to find a feasible solution as good as S^* in parameterized time f(k)⋅n^O(1), where k denotes the distance |PΔ S^*|. This model generalizes numerous classical parameterized optimization problems whose parameter k is the minimum number of elements removed from U to make it feasible, which corresponds to the case P = U. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where U is the set of constraints, and a subset U' of constraints is feasible if there is an assignment to the variables satisfying all constraints in U'. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate’s acceptance depends on the number of true literals.

Cite as

Aditya Anand, Vincent Cohen-Addad, Tommaso D'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, and Sijin Peng. Complexity of Local Search for CSPs Parameterized by Constraint Difference. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.IPEC.2025.26,
  author =	{Anand, Aditya and Cohen-Addad, Vincent and D'Orsi, Tommaso and Gupta, Anupam and Lee, Euiwoong and Panigrahi, Debmalya and Peng, Sijin},
  title =	{{Complexity of Local Search for CSPs Parameterized by Constraint Difference}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.26},
  URN =		{urn:nbn:de:0030-drops-251586},
  doi =		{10.4230/LIPIcs.IPEC.2025.26},
  annote =	{Keywords: Constraint Satisfaction Problems, Parameterized Local Search, Optimization}
}

Search Results

Documents authored by Peng, Sijin

On Tight FPT Time Approximation Algorithms for k-Clustering Problems

Abstract

Cite as

Complexity of Local Search for CSPs Parameterized by Constraint Difference

Abstract

Cite as

Thanks for your feedback!

Could not send message