3 papers
cs.DC2026
New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms
Sijin Peng
Local Computation Algorithms (LCAs), introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a special type of sublinear algorithms that, given probing access to a possibly mass…
cs.DS2026
On Tight FPT Time Approximation Algorithms for k-Clustering Problems
Han Dai, Shi Li, Sijin Peng
Following recent advances in combining approximation algorithms with fixed-parameter tractability (FPT), we study FPT-time approximation algorithms for minimum-norm -clustering…
cs.DS2025
Complexity of Local Search for CSPs Parameterized by Constraint Difference
Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi +4
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…