Parinya Chalermsook

Fateme Abbasi, Sandip Banerjee, Jarosław Byrka et al.

This paper considers the well-studied algorithmic regime of designing a $(1+ε)$-approximation algorithm for a $k$-clustering problem that runs in time $f(k,ε)poly(n)$ (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for $k$-center [Badŏiu, Har-Peled, Indyk; STOC'02] as well as $k$-median, and $k$-means [Kumar, Sabharwal, Sen; J. ACM 2010]. However, existing EPASes handle only basic objectives (such as $k$-center, $k$-median, and $k$-means) and are tailored to the specific objective and metric space. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. Our algorithm gives EPASes for a large variety of clustering objectives (for example, $k$-means, $k$-center, $k$-median, priority $k$-center, $\ell$-centrum, ordered $k$-median, socially fair $k$-median aka robust $k$-median, or more generally monotone norm $k$-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics). Key to our approach is a new concept that we call bounded $ε$-scatter dimension--an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension. Our main technical result shows that two conditions are essentially sufficient for our algorithm to yield an EPAS on the input metric $M$ for any clustering objective: (i) The objective is described by a monotone (not necessarily symmetric!) norm, and (ii) the $ε$-scatter dimension of $M$ is upper bounded by a function of $ε$.

Lotte Blank, Karl Bringmann, Parinya Chalermsook et al.

In the (continuous) Euclidean $k$-center problem, given $n$ points in $\mathbb{R}^d$ and an integer $k$, the goal is to find $k$ center points in $\mathbb{R}^d$ that minimize the maximum Euclidean distance from any input point to its closest center. In this paper, we establish conditional lower bounds for this problem in constant dimensions in two settings. $\bullet$ Parameterized by $k$: Assuming the Exponential Time Hypothesis (ETH), we show that there is no $f(k)n^{o(k^{1-1/d})}$-time algorithm for the Euclidean $k$-center problem. This result shows that the algorithm of Agarwal and Procopiuc [SODA 1998; Algorithmica 2002] is essentially optimal. Furthermore, our lower bound rules out any $(1+\varepsilon)$-approximation algorithm running in time $(k/\varepsilon)^{o(k^{1-1/d})}n^{O(1)}$, thereby establishing near-optimality of the corresponding approximation scheme by the same authors. $\bullet$ Small $k$: Assuming the 3-SUM hypothesis, we prove that for any $\varepsilon>0$ there is no $O(n^{2-\varepsilon})$-time algorithm for the Euclidean $2$-center problem in $\mathbb{R}^3$. This settles an open question posed by Agarwal, Ben Avraham, and Sharir [SoCG 2010; Computational Geometry 2013]. In addition, under the same hypothesis, we prove that for any $\varepsilon > 0$, the Euclidean $6$-center problem in $\mathbb{R}^2$ also admits no $O(n^{2-\varepsilon})$-time algorithm. The technical core of all our proofs is a novel geometric embedding of a system of linear equations. We construct a point set where each variable corresponds to a specific collection of points, and the geometric structure ensures that a small-radius clustering is possible if and only if the system has a valid solution.

Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer et al.

The dichromatic number $\vecχ(D)$ of a digraph is the minimum number $k$ such that $V(D)$ can be partitioned into $k$ subsets, each inducing an acyclic digraph. The acyclic number $\vecα(D)$ is the cardinality of a largest induced acyclic subdigraph of $D$. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating $\vecχ$ and $\vecα$ remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every $ε>0$, it is hard to approximate both $\vecα$ and $\vecχ$ up to a factor of $n^{1-ε}$ even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color $\ell$-dicolorable digraphs using at most $\ell \cdot n^{1-\frac{1}{\ell}}$ colors in time $O(n^{2\ell})$; in particular, we can color $2$-dicolorable digraphs with $2\sqrt{n}$ colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number $α$ of the underlying graph. We consider two special cases in this regard: digraphs with $\vecχ(D)\leq 2$ and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.

Fateme Abbasi, Sandip Banerjee, Jarosław Byrka et al.

We consider the well-studied Robust $(k, z)$-Clustering problem, which generalizes the classic $k$-Median, $k$-Means, and $k$-Center problems. Given a constant $z\ge 1$, the input to Robust $(k, z)$-Clustering is a set $P$ of $n$ weighted points in a metric space $(M,δ)$ and a positive integer $k$. Further, each point belongs to one (or more) of the $m$ many different groups $S_1,S_2,\ldots,S_m$. Our goal is to find a set $X$ of $k$ centers such that $\max_{i \in [m]} \sum_{p \in S_i} w(p) δ(p,X)^z$ is minimized. This problem arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For polynomial time computation, an approximation factor of $O(\log m/\log\log m)$ is known [Makarychev, Vakilian, COLT $2021$], which is tight under a plausible complexity assumption even in the line metrics. For FPT time, there is a $(3^z+ε)$-approximation algorithm, which is tight under GAP-ETH [Goyal, Jaiswal, Inf. Proc. Letters, 2023]. Motivated by the tight lower bounds for general discrete metrics, we focus on \emph{geometric} spaces such as the (discrete) high-dimensional Euclidean setting and metrics of low doubling dimension, which play an important role in data analysis applications. First, for a universal constant $η_0 >0.0006$, we devise a $3^z(1-η_{0})$-factor FPT approximation algorithm for discrete high-dimensional Euclidean spaces thereby bypassing the lower bound for general metrics. We complement this result by showing that even the special case of $k$-Center in dimension $Θ(\log n)$ is $(\sqrt{3/2}- o(1))$-hard to approximate for FPT algorithms. Finally, we complete the FPT approximation landscape by designing an FPT $(1+ε)$-approximation scheme (EPAS) for the metric of sub-logarithmic doubling dimension.