DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2026.12

Maximizing Diversity in (Near-)Median String Selection

Authors: Diptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit, and Aravinda Kanchana Ruwanpathirana

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract

Given a set of strings over a specified alphabet, identifying a median or consensus string that minimizes the total distance to all input strings is a fundamental data aggregation problem. When the Hamming distance is considered as the underlying metric, this problem has extensive applications, ranging from bioinformatics to pattern recognition. However, modern applications often require the generation of multiple (near-)optimal yet diverse median strings to enhance flexibility and robustness in decision-making. In this study, we address this need by focusing on two prominent diversity measures: sum dispersion and min dispersion. We first introduce an exact algorithm for the diameter variant of the problem, which identifies pairs of near-optimal medians that are maximally diverse. Subsequently, we propose a (1-ε)-approximation algorithm (for any ε > 0) for sum dispersion, as well as a bi-criteria approximation algorithm for the more challenging min dispersion case, allowing the generation of multiple (more than two) diverse near-optimal Hamming medians. Our approach primarily leverages structural insights into the Hamming median space and also draws on techniques from error-correcting code construction to establish these results.

Cite as

Diptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit, and Aravinda Kanchana Ruwanpathirana. Maximizing Diversity in (Near-)Median String Selection. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.CPM.2026.12,
  author =	{Chakraborty, Diptarka and Kundu, Rudrayan and Purohit, Nidhi and Ruwanpathirana, Aravinda Kanchana},
  title =	{{Maximizing Diversity in (Near-)Median String Selection}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.12},
  URN =		{urn:nbn:de:0030-drops-259382},
  doi =		{10.4230/LIPIcs.CPM.2026.12},
  annote =	{Keywords: Diversity maximization, Hamming median, diameter, dispersion, approximation algorithms}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.26

On the Parameterized Complexity of Min-Sum-Radii

Authors: Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, and Melanie Schmidt

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

In the Min-Sum-Radii (MSR) clustering problem, we are given a finite set X of n points in a metric space. The objective is to find at most k clusters centered at a subset of these points such that every point of X is assigned to one of the clusters, minimizing the sum of the radii of the clusters. The problem is known to be NP-hard even on metrics induced by weighted planar graphs and metrics with constant doubling dimension, as shown by Gibson et al. (SWAT 2008). In this work, we investigate the parameterized complexity of MSR on metrics induced by undirected graphs. We distinguish between weighted graph metrics (with positive edge weights) and unweighted graph metrics (where all edges have unit weight). Weighted Graph Metrics. We show that MSR is W[1]-hard on metrics induced by weighted bipartite graphs, when parameterized by the combined parameter k the number of clusters and Δ the cost of the clustering. We then investigate the structural parameterized complexity of the problem. Drexler et al. [doi:10.48550/arXiv.2310.02130] showed that the MSR problem admits an XP algorithm on metrics induced by weighted graphs when parameterized by treewidth, and asked whether this can be improved to fixed-parameter tractability. We first answer their question in the negative, and more strongly show that MSR stays W[1]-hard on metrics induced by undirected weighted bipartite graphs when parameterized by the vertex cover number plus k. We then turn our attention to parameters for dense graphs and show that MSR remains W[1]-hard when parameterized by k+Δ even on cliques and complete bipartite graphs. On the positive side, we employ the known XP algorithm parameterized by treewidth, to show that the MSR problem is FPT when parameterized by the parameter treewidth plus Δ. Together, these results provide a complete picture of the parameterized complexity of MSR with respect to any combination of parameters k, Δ, as well as structural parameters for sparse graphs above vertex cover and known parameters for dense graphs (such as neighborhood diversity and modular width). Unweighted Graph Metrics. The story is rather different for unweighted graphs, since it is a long standing open question whether MSR on metrics induced by undirected graphs is solvable in polynomial-time. Although we cannot answer this question, we provide classical and parameterized hardness results for two very closely related problems, namely Exact-MSR (MSR and one wants to find exactly k clusters) and Allowed-Centers-MSR (MSR with an additional set of allowed cluster centers). We also show that MSR as well as these two problems are fixed-parameter tractable parameterized by the treedepth of the input graph.

Cite as

Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, and Melanie Schmidt. On the Parameterized Complexity of Min-Sum-Radii. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.SWAT.2026.26,
  author =	{Kumar, Pankaj and M\"{u}ller, Haiko and Ordyniak, Sebastian and Schmidt, Melanie},
  title =	{{On the Parameterized Complexity of Min-Sum-Radii}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.26},
  URN =		{urn:nbn:de:0030-drops-260623},
  doi =		{10.4230/LIPIcs.SWAT.2026.26},
  annote =	{Keywords: Parameterized complexity, Min-Sum-Radii clustering}
}

Document

DOI: 10.4230/LIPIcs.FORC.2026.9

Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers

Authors: Rajni Dabas, Samir Khuller, and Emilie Rivkin

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract

Classical clustering problems such as Facility Location and k-Median aim to efficiently serve a set of clients from a subset of facilities - minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in k-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns, especially when the facilities correspond to critically needed facilities for emergencies such as fire stations, hospitals and other emergency services. We study Facility Location with Fair Outliers, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a O(1/ε) approximation factor and (1+ 2ε) factor violation in outliers per group. For k-Median with Fair Outliers, we design a bicriteria approximation with a 4(1+ω/ε) approximation factor and (ω + ε) violation in outliers per group improving on prior work by avoiding dependence on k in outlier violations. We also prove that the problems are W[1]-hard parameterized by ω. We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice.

Cite as

Rajni Dabas, Samir Khuller, and Emilie Rivkin. Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dabas_et_al:LIPIcs.FORC.2026.9,
  author =	{Dabas, Rajni and Khuller, Samir and Rivkin, Emilie},
  title =	{{Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.9},
  URN =		{urn:nbn:de:0030-drops-259812},
  doi =		{10.4230/LIPIcs.FORC.2026.9},
  annote =	{Keywords: Approximation algorithms, fairness}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.14

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems

Authors: Sujoy Bhore, Anupam Gupta, and Amit Kumar

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

In the online hitting set problem, sets arrive over time, and the algorithm has to maintain a subset of elements that hit all the sets seen so far. Alon, Awerbuch, Azar, Buchbinder, and Naor (SICOMP 2009) gave an algorithm with competitive ratio O(log n log m) for the (general) online hitting set and set cover problems for m sets and n elements; this is known to be tight for efficient online algorithms. Given this barrier for general set systems, we ask: can we break this double-logarithmic phenomenon for online hitting set/set cover on structured and geometric set systems? We provide an O(log n log log n)-competitive algorithm for the weighted online hitting set problem on set systems with linear shallow-cell complexity, replacing the double-logarithmic factor in the general result by effectively a single logarithmic term. As a consequence of our results we obtain the first bounds for weighted online hitting set for natural geometric set families, thereby answering open questions regarding the gap between general and geometric weighted online hitting set problems.

Cite as

Sujoy Bhore, Anupam Gupta, and Amit Kumar. Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.14,
  author =	{Bhore, Sujoy and Gupta, Anupam and Kumar, Amit},
  title =	{{Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.14},
  URN =		{urn:nbn:de:0030-drops-258206},
  doi =		{10.4230/LIPIcs.SoCG.2026.14},
  annote =	{Keywords: Hitting Set, Online Algorithms, Shallow-Cell Complexity, VC-Dimension}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.24

Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support

Authors: Reilly Browne and Hsien-Chih Chang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

Given an unweighted graph G, the minimum r-dominating set problem asks for a subset of vertices S of the smallest cardinality, such that every vertex in G is within radius r to some vertex in S. While the r-dominating set problem on planar graph admits PTAS from Baker’s shifting/layering technique when r is a constant, the problem becomes significantly harder when r can depend on n. In fact, under Exponential-Time Hypothesis, Fox-Epstein ηl [SODA 2019] observed that no efficient PTAS can exist for the unbounded r-dominating set problem on planar graphs. One may consider even harder weighted-variant known as the vertex-weighted metric r-dominating set, where edges are associated with lengths, and every vertex is associated with a positive-valued weight, and the goal is to compute an r-dominating set with minimum total weight. As a result, people resorted to bicriteria algorithms by allowing the returned solution to use radius-(1+ε)r balls instead, in addition to the total weight being a 1+ε approximation to the optimal value. We establish the first single-criteria polynomial-time O(1)-approximation algorithm for the vertex-weighted metric r-dominating set problem on planar graphs when r is part of the input, and can be arbitrarily large compared to n. Our new (single-criteria) O(1)-approximation algorithm uses the quasi-uniformity sampling technique of Chan et al. [SODA 2012] by bounding the shallow cell complexity of the (unbounded) radius-r ball system to be linear in n. To this end we have two technical innovations: 1) The discrete ball system on planar graphs are neither pseudodisks nor have well-defined boundaries for standard union-complexity arguments. We construct a support graph for arbitrary distance ball systems as contractions of Voronoi cells; the sparseness comes as a byproduct. 2) We present an assignment of each depth-(≥3) cell to a unique 3-tuple of ball centers. This allows us to use standard Clarkson-Shor techniques to reduce the counting to cells of depth exactly 3, which we prove to be size O(n) by a novel geometric argument based on our support being a Voronoi contraction.

Cite as

Reilly Browne and Hsien-Chih Chang. Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{browne_et_al:LIPIcs.SoCG.2026.24,
  author =	{Browne, Reilly and Chang, Hsien-Chih},
  title =	{{Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.24},
  URN =		{urn:nbn:de:0030-drops-258300},
  doi =		{10.4230/LIPIcs.SoCG.2026.24},
  annote =	{Keywords: Minimum dominating set, planar graphs, shallow cell complexity}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.31

Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems

Authors: Chaeyoon Chung, Anil Maheshwari, and Michiel Smid

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

Given a set S of n points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in S to its closest line. We present a (1+ε)-approximation algorithm for the two-line-center problem that runs in O((n/ε) log (1/ε)) time, which improves the previously best O(nlog n + (n/ε²) log (1/ε) + (1/ε³)log (1/ε))-time algorithm. We also consider three variants of this problem, in which the orientations of the two lines are restricted: (1) the orientation of one of the two lines is fixed, (2) the orientations of both lines are fixed, and (3) the two lines are required to be parallel. For each of these three variants, we give the first (1+ε)-approximation algorithm that runs in linear time. In particular, for the variant where the orientation of one of the two lines is fixed, we also give an improved exact algorithm that runs in O(n log n) time and show that it is optimal.

Cite as

Chaeyoon Chung, Anil Maheshwari, and Michiel Smid. Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.SoCG.2026.31,
  author =	{Chung, Chaeyoon and Maheshwari, Anil and Smid, Michiel},
  title =	{{Linear-Time (1+\epsilon)-Approximation Algorithms for Two-Line-Center Problems}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.31},
  URN =		{urn:nbn:de:0030-drops-258374},
  doi =		{10.4230/LIPIcs.SoCG.2026.31},
  annote =	{Keywords: Approximation algorithm, two-line-center problem, k-line-center problem, projective clustering, \epsilon-certificate, \epsilon-coreset, width of a point set}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.33

Near-Optimal Bounds for Parameterized Euclidean k-Means

Authors: Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

The k-means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find k representative points so as to minimize the sum of the squared distances from each point to its closest representative. In this work, we study the approximability of k-means in Euclidean spaces parameterized by the number of clusters, k. In seminal works, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] showed how to obtain a (1+ε)-approximation for high-dimensional Euclidean k-means in time 2^{(k/ε)^O(1)} ⋅ dn^O(1). In this work, we introduce a new fine-grained hypothesis called Exponential Time for Expanders Hypothesis (XXH) which roughly asserts that there are no non-trivial exponential time approximation algorithms for the vertex cover problem on near perfect vertex expanders. Assuming XXH, we close the above long line of work on approximating Euclidean k-means by showing that there is no 2^{(k/ε)^{1-o(1)}} ⋅ n^O(1) time algorithm achieving a (1+ε)-approximation for k-means in Euclidean space. This lower bound is tight as it matches the algorithm given by Feldman, Monemizadeh, and Sohler [SoCG'07] whose runtime is 2^O(k/ε) + O(ndk). Furthermore, assuming XXH, we show that the seminal O(n^{kd+1}) runtime exact algorithm of Inaba, Katoh, and Imai [SoCG'94] for k-means is optimal for small values of k.

Cite as

Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn. Near-Optimal Bounds for Parameterized Euclidean k-Means. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2026.33,
  author =	{Cohen-Addad, Vincent and C. S., Karthik and Saulpic, David and Schwiegelshohn, Chris},
  title =	{{Near-Optimal Bounds for Parameterized Euclidean k-Means}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.33},
  URN =		{urn:nbn:de:0030-drops-258391},
  doi =		{10.4230/LIPIcs.SoCG.2026.33},
  annote =	{Keywords: k-means clustering, Euclidean space, Fine-Grained Complexity}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.34

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces

Authors: Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

The k-median and k-means clustering objectives are classic objectives for modeling clustering in a metric space. Given a set of points in a metric space, the goal of the k-median (resp. k-means) problem is to find k representative points so as to minimize the sum of the distances (resp. sum of squared distances) from each point to its closest representative. Cohen-Addad, Feldmann, and Saulpic [JACM'21] showed how to obtain a (1+ε)-factor approximation in low-dimensional Euclidean metric for both the k-median and k-means problems in near-linear time 2^{(1/ε)^O(d²)} n ⋅ polylog(n) (where d is the dimension and n is the number of input points). We improve this running time to 2^{O(1/ε)^{d-1}} ⋅ n ⋅ polylog(n), and show an almost matching lower bound: under the Gap Exponential Time Hypothesis for 3-SAT, there is no 2^o(1/ε^{d-1}) n^O(1) algorithm achieving a (1+ε)-approximation for k-means.

Cite as

Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn. Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2026.34,
  author =	{Cohen-Addad, Vincent and Karthik C. S. and Saulpic, David and Schwiegelshohn, Chris},
  title =	{{Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.34},
  URN =		{urn:nbn:de:0030-drops-258404},
  doi =		{10.4230/LIPIcs.SoCG.2026.34},
  annote =	{Keywords: k-means clustering, k-median clustering, Euclidean space, Fine-Grained Complexity}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.48

FPT Approximations for Capacitated Sum of Radii and Diameters

Authors: Arnold Filtser and Ameet Gadekar

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

The Capacitated Sum of Radii problem involves partitioning a set of points P, where each point p ∈ P has capacity U_p, into k clusters that minimize the sum of cluster radii, such that the number of points in the cluster centered at point p is at most U_p. We begin by showing that the problem is APX-hard, and that under gap-ETH there is no parameterized approximation scheme (FPT-AS). We then construct a ≈5.83-approximation algorithm in FPT time (improving a previous ≈7.61 approximation in FPT time). Our results also hold when the objective is a general monotone symmetric norm of radii. We also improve the approximation factors for the uniform capacity case, and for the closely related problem of Capacitated Sum of Diameters.

Cite as

Arnold Filtser and Ameet Gadekar. FPT Approximations for Capacitated Sum of Radii and Diameters. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.SoCG.2026.48,
  author =	{Filtser, Arnold and Gadekar, Ameet},
  title =	{{FPT Approximations for Capacitated Sum of Radii and Diameters}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.48},
  URN =		{urn:nbn:de:0030-drops-258545},
  doi =		{10.4230/LIPIcs.SoCG.2026.48},
  annote =	{Keywords: clustering, sum of radii, sum of diameter, capacitated clustering, fpt}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.13

Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].

Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2025.8

Binary k-Center with Missing Entries: Structure Leads to Tractability

Authors: Tobias Friedrich, Kirill Simonov, and Farehe Soheil

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

Abstract

k-Center clustering is a fundamental classification problem, where the task is to categorize the given collection of entities into k clusters and come up with a representative for each cluster, so that the maximum distance between an entity and its representative is minimized. In this work, we focus on the setting where the entities are represented by binary vectors with missing entries, which model incomplete categorical data. This version of the problem has wide applications, from predictive analytics to bioinformatics. Our main finding is that the problem, which is notoriously hard from the classical complexity viewpoint, becomes tractable as soon as the known entries are sparse and exhibit a certain structure. Formally, we show fixed-parameter tractable algorithms for the parameters vertex cover, fracture number, and treewidth of the row-column graph, which encodes the positions of the known entries of the matrix. Additionally, we tie the complexity of the 1-cluster variant of the problem, which is famous under the name Closest String, to the complexity of solving integer linear programs with few constraints. This implies, in particular, that improving upon the running times of our algorithms would lead to more efficient algorithms for integer linear programming in general.

Cite as

Tobias Friedrich, Kirill Simonov, and Farehe Soheil. Binary k-Center with Missing Entries: Structure Leads to Tractability. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.IPEC.2025.8,
  author =	{Friedrich, Tobias and Simonov, Kirill and Soheil, Farehe},
  title =	{{Binary k-Center with Missing Entries: Structure Leads to Tractability}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-251403},
  doi =		{10.4230/LIPIcs.IPEC.2025.8},
  annote =	{Keywords: Clustering, Missing Entries, k-Center, Parameterized Algorithms}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.46

Max-Distance Sparsification for Diversification and Clustering

Authors: Soh Kumabe

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

Let 𝒟 be a set family that is the solution domain of some combinatorial problem. The max-min diversification problem on 𝒟 is the problem to select k sets from 𝒟 such that the Hamming distance between any two selected sets is at least d. FPT algorithms parameterized by k+𝓁, where 𝓁 = max_{D ∈ 𝒟}|D|, and k+d have been actively studied recently for several specific domains. This paper provides unified algorithmic frameworks to solve this problem. Specifically, for each parameterization k+𝓁 and k+d, we provide an FPT oracle algorithm for the max-min diversification problem using oracles related to 𝒟. We then demonstrate that our frameworks provide the first FPT algorithms on several new domains 𝒟, including the domain of t-linear matroid intersection, almost 2-SAT, minimum edge s,t-flows, vertex sets of s,t-mincut, vertex sets of edge bipartization, and Steiner trees. We also demonstrate that our frameworks generalize most of the existing domain-specific tractability results. Our main technical breakthrough is introducing the notion of max-distance sparsifier of 𝒟, a domain on which the max-min diversification problem is equivalent to the same problem on the original domain 𝒟. The core of our framework is to design FPT oracle algorithms that construct a constant-size max-distance sparsifier of 𝒟. Using max-distance sparsifiers, we provide FPT algorithms for the max-min and max-sum diversification problems on 𝒟, as well as k-center and k-sum-of-radii clustering problems on 𝒟, which are also natural problems in the context of diversification and have their own interests.

Cite as

Soh Kumabe. Max-Distance Sparsification for Diversification and Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumabe:LIPIcs.ESA.2025.46,
  author =	{Kumabe, Soh},
  title =	{{Max-Distance Sparsification for Diversification and Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.46},
  URN =		{urn:nbn:de:0030-drops-245146},
  doi =		{10.4230/LIPIcs.ESA.2025.46},
  annote =	{Keywords: Fixed-Parameter Tractability, Diversification, Clustering}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.62

Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering

Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

In a seminal work, Chierichetti et al. [Chierichetti et al., 2017] introduced the (t,k)-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most t times and at least 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O(1)- and O(t)-approximation for the k-center and the k-median objective, respectively. Recently, Carta et al. [Carta et al., 2024] studied this problem with the sum-of-radii objective and obtained a (6+ε)-approximation with running time O((k log_{1+ε}(k/ε))^k n^O(1)), i.e., fixed-parameter tractable in k. Here n is the input size. In this work, we design the first polynomial-time O(1)-approximation for (t,k)-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as k-center, that admit polynomial-time O(1)-approximations. This result also implies a polynomial-time O(1)-approximation for the Euclidean version of the problem, for which an f(k)⋅n^O(1)-time (1+ε)-approximation was known due to Drexler et al. [Drexler et al., 2023]. Here f is an exponential function of k. We are also able to extend our result to any arbitrary 𝓁 ≥ 2 number of colors when t = 1. This matches known results for the k-center and k-median objectives in this case. The significant disparity of sum-of-radii compared to k-center and k-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.

Cite as

Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen. Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bagherinezhad_et_al:LIPIcs.ESA.2025.62,
  author =	{Bagheri Nezhad, Sina and Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{62:1--62:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.62},
  URN =		{urn:nbn:de:0030-drops-245309},
  doi =		{10.4230/LIPIcs.ESA.2025.62},
  annote =	{Keywords: fair clustering, sum-of-radii clustering, approximation algorithms}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.67

Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.

Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.58

Streaming Diameter of High-Dimensional Points

Authors: Magnús M. Halldórsson, Nicolaos Matsakis, and Pavel Veselý

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

We improve the space bound for streaming approximation of Diameter but also of Farthest Neighbor queries, Minimum Enclosing Ball and its Coreset, in high-dimensional Euclidean spaces. In particular, our deterministic streaming algorithms store 𝒪(ε^{-2}log(1/(ε))) points. This improves by a factor of ε^{-1} the previous space bound of Agarwal and Sharathkumar (SODA 2010), while retaining the state-of-the-art approximation guarantees, such as √2+ε for Diameter or Farthest Neighbor queries, and also offering a simpler and more complete argument. Moreover, we show that storing Ω(ε^{-1}) points is necessary for a streaming (√2+ε)-approximation of Farthest Pair and Farthest Neighbor queries.

Cite as

Magnús M. Halldórsson, Nicolaos Matsakis, and Pavel Veselý. Streaming Diameter of High-Dimensional Points. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 58:1-58:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.ESA.2025.58,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Matsakis, Nicolaos and Vesel\'{y}, Pavel},
  title =	{{Streaming Diameter of High-Dimensional Points}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{58:1--58:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.58},
  URN =		{urn:nbn:de:0030-drops-245263},
  doi =		{10.4230/LIPIcs.ESA.2025.58},
  annote =	{Keywords: streaming algorithm, farthest pair, diameter, minimum enclosing ball, coreset}
}

41 Search Results for "Varadarajan, Kasturi R."

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message