Evangelos Kipouridis

Anita Dürr, Evangelos Kipouridis, Michael Lampis et al.

In the Orthogonal Vectors problem (OV), we are given two families $A, B$ of subsets of $\{1,\ldots,d\}$, each of size $n$, and the task is to decide whether there exists a pair $a \in A$ and $b \in B$ such that $a \cap b = \emptyset$. Straightforward algorithms for this problem run in $\mathcal{O}(n^2 \cdot d)$ or $\mathcal{O}(2^d \cdot n)$ time, and assuming SETH, there is no $2^{o(d)}\cdot n^{2-\varepsilon}$ time algorithm that solves this problem for any constant $\varepsilon > 0$. Williams (FOCS 2024) presented a $\tilde{\mathcal{O}}(1.35^d \cdot n)$-time algorithm for the problem, based on the succinct equality-rank decomposition of the disjointness matrix. In this paper, we present a combinatorial algorithm that runs in randomized time $\tilde{\mathcal{O}}(1.25^d n)$. This can be improved to $\mathcal{O}(1.16^d \cdot n)$ using computer-aided evaluations. We generalize our result to the $k$-Orthogonal Vectors problem, where given $k$ families $A_1,\ldots,A_k$ of subsets of $\{1,\ldots,d\}$, each of size $n$, the task is to find elements $a_i \in A_i$ for every $i \in \{1,\ldots,k\}$ such that $a_1 \cap a_2 \cap \ldots \cap a_k = \emptyset$. We show that for every fixed $k \ge 2$, there exists $\varepsilon_k > 0$ such that the $k$-OV problem can be solved in time $\mathcal{O}(2^{(1 - \varepsilon_k)\cdot d}\cdot n)$. We also show that, asymptotically, this is the best we can hope for: for any $\varepsilon > 0$ there exists a $k \ge 2$ such that $2^{(1 - \varepsilon)\cdot d} \cdot n^{\mathcal{O}(1)}$ time algorithm for $k$-Orthogonal Vectors would contradict the Set Cover Conjecture.

Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas et al.

Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2025] showed that for any fixed $k$, the $k$-edge connected components of an undirected graph can be computed in linear time. In contrast, the directed case remains significantly more challenging: linear-time algorithms are only known for $k \le 3$, and for any fixed $k > 3$, the best known bound for sparse or moderately dense graphs is still the $O(mn)$-time algorithm of Nagamochi and Watanabe (1993). In this paper, we break the $O(mn)$ barrier for all $k = o(n^{1/4}/\sqrt{\log{n}})$. We present a randomized algorithm that computes the $(k+2)$-edge-connected components of a $k$-edge-connected directed graph in $O(k^2 m \sqrt{n} \log n)$ time, for any~$k$. This constitutes the first improvement over the classic Nagamochi--Watanabe bound for any constant $k > 3$. Our approach introduces new structural insights into directed edge-cuts and combines these with both new and existing techniques. A central contribution of our work is a substantial simplification and generalization of the framework introduced in~\cite{GKPP:3ECC}, which achieved an $\widetilde{O}(m\sqrt{m})$ bound for computing the $3$-edge-connected components of a digraph. In addition, we develop a variant of our algorithm that achieves the same $O(m \sqrt{n} \log n)$ running time for computing the $4$-edge-connected components of a \emph{general} directed graph.

Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase

We revisit the $(f,g)$-clustering problem that we introduced in a recent work [SODA'25], and which subsumes fundamental clustering problems such as $k$-Center, $k$-Median, Min-Sum of Radii, and Min-Load $k$-Clustering. This problem assigns each of the $k$ clusters a cost determined by the monotone, symmetric norm $f$ applied to the vector distances in the cluster, and aims at minimizing the norm $g$ applied to the vector of cluster costs. Previously, we focused on certain special cases for which we designed constant-factor approximation algorithms. Our bounds for more general settings left, however, large gaps to the known bounds for the basic problems they capture. In this work, we provide a clearer picture of the approximability of these more general settings. First, we design an $O(\log^2 n)$-approximation algorithm for $(f, L_{1})$-clustering for any $f$. This improves upon our previous $\widetilde{O}(\sqrt{n})$-approximation. Second, we provide an $O(k)$-approximation for the general $(f,g)$-clustering problem, which improves upon our previous $\widetilde{O}(\sqrt{kn})$-approximation algorithm and matches the best-known upper bound for Min-Load $k$-Clustering. We then design an approximation algorithm for $(f,g)$-clustering that interpolates, up to polylog factors, between the best known bounds for $k$-Center, $k$-Median, Min-Sum of Radii, Min-Load $k$-Clustering, (Top, $L_{1}$)-clustering, and $(L_{\infty},g)$-clustering based on a newly defined parameter of $f$ and $g$.

Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase

We initiate the study of the following general clustering problem. We seek to partition a given set $P$ of data points into $k$ clusters by finding a set $X$ of $k$ centers and assigning each data point to one of the centers. The cost of a cluster, represented by a center $x\in X$, is a monotone, symmetric norm $f$ (inner norm) of the vector of distances of points assigned to $x$. The goal is to minimize a norm $g$ (outer norm) of the vector of cluster costs. This problem, which we call $(f,g)$-Clustering, generalizes many fundamental clustering problems such as $k$-Center, $k$-Median , Min-Sum of Radii, and Min-Load $k$-Clustering . A recent line of research (Chakrabarty, Swamy [STOC'19]) studies norm objectives that are oblivious to the cluster structure such as $k$-Median and $k$-Center. In contrast, our problem models cluster-aware objectives including Min-Sum of Radii and Min-Load $k$-Clustering. Our main results are as follows. First, we design a constant-factor approximation algorithm for $(\textsf{top}_\ell,\mathcal{L}_1)$-Clustering where the inner norm ($\textsf{top}_\ell$) sums over the $\ell$ largest distances. Second, we design a constant-factor approximation\ for $(\mathcal{L}_\infty,\textsf{Ord})$-Clustering where the outer norm is a convex combination of $\textsf{top}_\ell$ norms (ordered weighted norm).