In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of k base curves of length at most l such that the sum of Fréchet distances of the time series to a "Fréchet combination" of the base curves is minimized. Here, a Fréchet combination allows to combine individually scaled base curves using a k-dimensional traversal. We call the problem of finding a set of optimal base curves the Fréchet decomposition problem and we consider two variants: (a) the base curves can be arbitrary curves of bounded length and (b) the curves come from a given finite set of candidate curves. We think of the Fréchet decomposition problem as a Fréchet variant of principal component analysis. For the case of a single base curve we develop a (1+ε)-approximation algorithm for the Fréchet decomposition problem. Additionally we give an exact algorithm for the projection distance problem that asks to compute the distance of one given time series to a given set of k base curves. This allows us to design an exact algorithm for the Fréchet decomposition problem for general k when curves come from a fixed candidate set.

In the metric k-median problem we are given a finite metric space (X∪ Y, 𝐝) and the objective is to compute a set of k centers C ⊆ Y that minimizes ∑_{p ∈ X} min_{c ∈ C} 𝐝(p,c). In general metric spaces, the best polynomial time algorithm, which is due to Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson [Vincent Cohen-Addad et al., 2025], computes a (2+ε)-approximation for arbitrary constant ε > 0. However, if the metric space has bounded doubling dimension, a near linear time (1+ε)-approximation algorithm is known due to the work of Cohen-Addad, Feldmann, and Saulpic [Vincent Cohen{-}Addad et al., 2021]. In this paper, we show that the (1+ε)-approximation algorithm can be generalized to the case when either X or Y has bounded doubling dimension (but the other set not). The case when X has bounded doubling dimension is motivated by the assumption that even though X is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when Y has bounded doubling dimension is perhaps more natural. It is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the (k,𝓁)-median problem under discrete Fréchet distance when 𝓁 is constant. The latter problem is a version of the k-median problem under Fréchet distance when the input consists of time series of z reals and where the centers are time series of 𝓁 reals [Anne Driemel et al., 2016]. Previously, for this problem no (1+ε)-approximation algorithm with running time polynomial in k was known. We also introduce a novel complexity reduction for time series of real values that leads to a similar result for the case of discrete Fréchet distance. In order to solve the case when Y has a bounded doubling dimension, we introduce a form of dimension reduction that replaces points from X by sets of points in Y. To solve the case when X has a bounded doubling dimension, we generalize Talwar’s decomposition [Kunal Talwar, 2004] of doubling metrics to our setting. The running time of our algorithms is 2^{2^t} Õ(n+m) where t = O(ddim log ddim/ε) and where ddim is the doubling dimension of X (resp. Y). The results also extend to the metric (uncapacitated) facility location problem. We believe that our techniques are likely applicable to other problems.

We study the $k$-center problem in the context of individual fairness. Let $P$ be a set of $n$ points in a metric space and $r_x$ be the distance between $x \in P$ and its $\lceil n/k \rceil$-th nearest neighbor. The problem asks to optimize the $k$-center objective under the constraint that, for every point $x$, there is a center within distance $r_x$. We give bicriteria $(\beta,\gamma)$-approximation algorithms that compute clusterings such that every point $x \in P$ has a center within distance $\beta r_x$ and the clustering cost is at most $\gamma$ times the optimal cost. Our main contributions are a deterministic $O(n^2+ kn \log n)$ time $(2,2)$-approximation algorithm and a randomized $O(nk\log(n/\delta)+k^2/\varepsilon)$ time $(10,2+\varepsilon)$-approximation algorithm, where $\delta$ denotes the failure probability. For the latter, we develop a randomized sampling procedure to compute constant factor approximations for the values $r_x$ for all $x\in P$ in subquadratic time; we believe this procedure to be of independent interest within the context of individual fairness.