19 Search Results for "Bercea, Ioana O."

Document
DOI: 10.4230/LIPIcs.SWAT.2026.4
Improved Bounds for Online TSP on the Half-Line

Authors: Júlia Baligács, Yann Disser, and Linda Thelen

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

Abstract
In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a 2-competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of 2.04. We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below 2. We introduce a second algorithm that beats the barrier of 2 by carefully modulating its speed, and prove a tight bound of 1.75 on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from 1.627 to 1.646.
Cite as

Júlia Baligács, Yann Disser, and Linda Thelen. Improved Bounds for Online TSP on the Half-Line. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.SWAT.2026.4,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Thelen, Linda},
  title =	{{Improved Bounds for Online TSP on the Half-Line}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{4:1--4:17},
  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.4},
  URN =		{urn:nbn:de:0030-drops-260402},
  doi =		{10.4230/LIPIcs.SWAT.2026.4},
  annote =	{Keywords: online algorithms, competitive analysis, server problems, online TSP}
}
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.SoCG.2026.52
Online Packing of Orthogonal Polygons

Authors: Tim Gerlach, Benjamin Hennies, and Linda Kleist

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

Abstract
While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insights that convex polygons do not allow for constant competitive online algorithms for diverse variants under translation, we study orthogonal polygons, in particular of small complexity. For translational packings of orthogonal 6-gons, we show that the competitive ratio of any online algorithm that aims to pack the items into a minimal number of unit bins is in Ω(n/(log n)), where n denotes the number of objects. In contrast, we show that constant competitive algorithms exist when the orthogonal 6-gons are symmetric or small. For (orthogonally convex) orthogonal 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible, i.e., every online algorithm has an asymptotic competitive ratio of at least n. This implies that for general orthogonal polygons, the trivial algorithm is best possible. Interestingly, for packing degenerate orthogonal polygons (with thickness 0), called skeletons, the change in complexity is even more drastic. While constant competitive algorithms for 6-skeletons exist, no online algorithm for 8-skeletons achieves a competitive ratio better than n. For other packing variants of orthogonal 6-gons under translation, our insights imply the following consequences. The asymptotic competitive ratio of any online algorithm is in Ω(n/(log n)) for strip packing, and there exist online algorithms with competitive ratios in O(1) for perimeter packing, or in O(√n) for minimizing the area of the bounding box. Moreover, the critical packing density is positive (if every object individually fits into the interior of a unit bin).
Cite as

Tim Gerlach, Benjamin Hennies, and Linda Kleist. Online Packing of Orthogonal Polygons. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gerlach_et_al:LIPIcs.SoCG.2026.52,
  author =	{Gerlach, Tim and Hennies, Benjamin and Kleist, Linda},
  title =	{{Online Packing of Orthogonal Polygons}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{52:1--52: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.52},
  URN =		{urn:nbn:de:0030-drops-258589},
  doi =		{10.4230/LIPIcs.SoCG.2026.52},
  annote =	{Keywords: Packing, orthogonal polygon, algorithm, offline, online, competitive ratio, bin packing, strip packing, perimeter packing, critical density, 6-gon, 8-gon, L-shape, Z-shape, skeleton}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.58
A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP

Authors: Andreas Kalavas, Charalampos Platanos, and Thanos Tolias

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

Abstract
In Online Sorting, an array of n initially empty cells is given. At each time step t, an element x_t ∈ [0,1] arrives and must be irrevocably placed in an empty cell without knowledge of future arrivals. We aim to minimize the sum of absolute differences between pairs of elements placed in consecutive array cells, seeking an online placement strategy that results in a final array close to a sorted one. An interesting multidimensional generalization, referred to as the Online Traveling Salesperson Problem, arises when the request sequence consists of points in the d-dimensional unit cube and the objective is to minimize the sum of Euclidean distances between points in consecutive cells. Motivated by the recent work of (Abrahamsen, Bercea, Beretta, Klausen and Kozma; ESA 2024), we consider the stochastic version of Online Sorting (resp. Online TSP), where each element (resp. point) x_t is an i.i.d. sample from the uniform distribution on [0, 1] (resp. [0,1]^d). By carefully decomposing the request sequence into a hierarchy of balls-into-bins instances, where the balls to bins ratio is large enough so that bin occupancy is sharply concentrated around its mean and small enough so that we can efficiently deal with the elements placed in the same bin, we obtain an online algorithm that approximates the optimal cost within a factor of O(log² n) with high probability. Our result comprises an exponential improvement over the previously best known competitive ratio of Õ(n^{1/4}) for Stochastic Online Sorting due to (Abrahamsen et al.; ESA 2024) and O(√n) for (adversarial) Online TSP due to (Bertram, ESA 2025).
Cite as

Andreas Kalavas, Charalampos Platanos, and Thanos Tolias. A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalavas_et_al:LIPIcs.STACS.2026.58,
  author =	{Kalavas, Andreas and Platanos, Charalampos and Tolias, Thanos},
  title =	{{A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{58:1--58:17},
  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.58},
  URN =		{urn:nbn:de:0030-drops-255473},
  doi =		{10.4230/LIPIcs.STACS.2026.58},
  annote =	{Keywords: sorting, online algorithm, balls-into-bins, TSP}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.107
New Greedy Spanners and Applications

Authors: Elizaveta Popova and Elad Tzalik

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We present a simple greedy procedure to compute an (α,β)-spanner for a graph G. We then show that this procedure is useful for building fault-tolerant spanners, as well as spanners for weighted graphs. Our first main result is an algorithm that, given a multigraph G, outputs an f edge fault-tolerant (k,k-1)-spanner H of size O(fn^{1+1/k}) which is tight. To our knowledge, this is the first tight result concerning the price of fault tolerance in spanners which are not multiplicative, in any model of faults. Our second main result is a new construction of a spanner for weighted graphs. We show that any weighted graph G has a subgraph H with O(n^{1+1/k}) edges such that any path P of hop-length 𝓁 in G has a replacement path P' in H of weighted length ≤ w(P)+(2k-2)w^(1/2)(P) where w(P) is the total edge weight of P, and w^(1/2) denotes the sum of the largest ⌈𝓁/2⌉ edge weights along P. Moreover, we show such approximation is optimal for shortest paths of hop-length 2. To our knowledge, this is the first construction of a "spanner" for weighted graphs that strictly improves upon the stretch of multiplicative (2k-1)-spanners for all non-adjacent vertex pairs, while maintaining the same size bound. Our technique is based on using clustering and ball-growing, which are methods commonly used in designing spanner algorithms, to analyze simple greedy algorithms. This allows us to combine the flexibility of clustering approaches with the unique properties of the greedy algorithm to get improved bounds. In particular, our methods give a very short proof that the parallel greedy spanner adds O(kn^{1+1/k}) edges, improving upon known bounds.
Cite as

Elizaveta Popova and Elad Tzalik. New Greedy Spanners and Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 107:1-107:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{popova_et_al:LIPIcs.ITCS.2026.107,
  author =	{Popova, Elizaveta and Tzalik, Elad},
  title =	{{New Greedy Spanners and Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{107:1--107:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.107},
  URN =		{urn:nbn:de:0030-drops-253945},
  doi =		{10.4230/LIPIcs.ITCS.2026.107},
  annote =	{Keywords: Graph Spanners, Greedy Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.5
External-Memory Priority Queues with Optimal Insertions

Authors: Gerth Stølting Brodal, Michael T. Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Nodari Sitchinava, and Rolf Svenning

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

Abstract
We present an external-memory priority queue structure supporting Insert and DeleteMin with amortized 𝒪(1) and 𝒪(lg N) comparisons, respectively, and amortized 𝒪(1/B) and 𝒪(1/B log_{M/B} N/B) I/Os, respectively. Here, M is the size of the internal memory, B is the block size of I/Os between internal and external memory, and N is the number of elements in the priority queue just before an operation is performed. Previous external-memory priority queues required amortized 𝒪(lg N) comparisons and 𝒪(1/B log_{M/B} N/B) I/Os for both Insert and DeleteMin. The construction requires the minimal assumption M ≥ 2B.
Cite as

Gerth Stølting Brodal, Michael T. Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Nodari Sitchinava, and Rolf Svenning. External-Memory Priority Queues with Optimal Insertions. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2025.5,
  author =	{Brodal, Gerth St{\o}lting and Goodrich, Michael T. and Iacono, John and Lo, Jared and Meyer, Ulrich and Pagan, Victor and Sitchinava, Nodari and Svenning, Rolf},
  title =	{{External-Memory Priority Queues with Optimal Insertions}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{5:1--5: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.5},
  URN =		{urn:nbn:de:0030-drops-244734},
  doi =		{10.4230/LIPIcs.ESA.2025.5},
  annote =	{Keywords: priority queues, external memory, cache aware, amortized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.80
Online Metric TSP

Authors: Christian Bertram

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

Abstract
In the online metric traveling salesperson problem, n points of a metric space arrive one by one and have to be placed (immediately and irrevocably) into empty cells of a size-n array. The goal is to minimize the sum of distances between consecutive points in the array. This problem was introduced by Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA'24] as a generalization of the online sorting problem, which was introduced by Aamand, Abrahamsen, Beretta, and Kleist [SODA'23] as a tool in their study of online geometric packing problems. Online metric TSP has been studied for a range of fixed metric spaces. For 1-dimensional Euclidean space, the problem is equivalent to online sorting, where an optimal competitive ratio of Θ(√n) is known. For d-dimensional Euclidean space, the best-known upper bound is O(2^d √{dn log n}), leaving a gap to the Ω(√n) lower bound. Finally, for the uniform metric, where all distances are 0 or 1, the optimal competitive ratio is known to be Θ(log n). We study the problem for a general metric space, presenting an algorithm with competitive ratio O(√n). In particular, we close the gap for d-dimensional Euclidean space, completely removing the dependence on dimension. One might hope to simultaneously guarantee competitive ratio O(√n) in general and O(log n) for the uniform metric, but we show that this is impossible.
Cite as

Christian Bertram. Online Metric TSP. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 80:1-80:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bertram:LIPIcs.ESA.2025.80,
  author =	{Bertram, Christian},
  title =	{{Online Metric TSP}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{80:1--80:9},
  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.80},
  URN =		{urn:nbn:de:0030-drops-245485},
  doi =		{10.4230/LIPIcs.ESA.2025.80},
  annote =	{Keywords: online algorithm, metric space, TSP}
}
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.63
Connected k-Median with Disjoint and Non-Disjoint Clusters

Authors: Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin, and Melanie Schmidt

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

Abstract
The connected k-median problem is a constrained clustering problem that combines distance-based k-clustering with connectivity information. The problem allows to input a metric space and an unweighted undirected connectivity graph that is completely unrelated to the metric space. The goal is to compute k centers and corresponding clusters such that each cluster forms a connected subgraph of G, and such that the k-median cost is minimized. The problem has applications in very different fields like geodesy (particularly districting), social network analysis (especially community detection), or bioinformatics. We study a version with overlapping clusters where points can be part of multiple clusters which is natural for the use case of community detection. This problem variant is Ω(log n)-hard to approximate, and our main result is an 𝒪(k² log n)-approximation algorithm for the problem. We complement it with an Ω(n^{1-ε})-hardness result for the case of disjoint clusters without overlap with general connectivity graphs, as well as an exact algorithm in this setting if the connectivity graph is a tree.
Cite as

Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin, and Melanie Schmidt. Connected k-Median with Disjoint and Non-Disjoint Clusters. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eube_et_al:LIPIcs.ESA.2025.63,
  author =	{Eube, Jan and Luo, Kelin and Reineccius, Dorian and R\"{o}glin, Heiko and Schmidt, Melanie},
  title =	{{Connected k-Median with Disjoint and Non-Disjoint Clusters}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{63:1--63: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.63},
  URN =		{urn:nbn:de:0030-drops-245317},
  doi =		{10.4230/LIPIcs.ESA.2025.63},
  annote =	{Keywords: Clustering, Connectivity constraints, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.104
Optimal Antimatroid Sorting

Authors: Benjamin Aram Berendsohn

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

Abstract
The classical comparison-based sorting problem asks us to find the underlying total ordering of a given set of elements, where we can only access the elements via comparisons. In this paper, we study a restricted version, where, as a hint, a set T of possible total orderings is given, usually in some compressed form. Recently, an algorithm called topological heapsort with optimal running time was found for case where T is the set of topological orderings of a given directed acyclic graph, or, equivalently, T is the set of linear extensions of a partial ordering [Haeupler et al. 2024]. We show that a simple generalization of topological heapsort is applicable to a much broader class of restricted sorting problems, where T corresponds to a given antimatroid. As a consequence, we obtain optimal algorithms for the following restricted sorting problems, where the allowed total orders are … - … restricted by a given set of monotone precedence formulas; - … the perfect elimination orders of a given chordal graph; or - … the possible vertex search orders of a given connected rooted graph.
Cite as

Benjamin Aram Berendsohn. Optimal Antimatroid Sorting. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 104:1-104:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{berendsohn:LIPIcs.ESA.2025.104,
  author =	{Berendsohn, Benjamin Aram},
  title =	{{Optimal Antimatroid Sorting}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{104:1--104: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.104},
  URN =		{urn:nbn:de:0030-drops-245735},
  doi =		{10.4230/LIPIcs.ESA.2025.104},
  annote =	{Keywords: sorting, working-set heap, greedy, antimatroid}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.23
Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints

Authors: Sayan Bandyapadhyay and Tianzhi Chen

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this work, we study k-min-sum-of-radii (k-MSR) clustering under mergeable constraints. k-MSR seeks to group data points using a set of up to k balls, such that the sum of the radii of the balls is minimized. A clustering constraint is called mergeable if merging two clusters satisfying the constraint, results in a cluster that also satisfies the constraint. Many popularly studied constraints are mergeable, including fairness constraints and lower bound constraints. In our work, we design a (4+ε)-approximation for k-MSR under any given mergeable constraint with runtime 2^{O(k/(ε)⋅log²k/ε)} n⁴, i.e., fixed-parameter tractable in k for constant ε. Our result directly improves upon the FPT (6+ε)-approximation by Carta et al. [Carta et al., 2024]. We also provide a hardness result that excludes the exact solvability of k-MSR under any given mergeable constraint in time f(k)n^o(k), assuming ETH is true.
Cite as

Sayan Bandyapadhyay and Tianzhi Chen. Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.APPROX/RANDOM.2025.23,
  author =	{Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.23},
  URN =		{urn:nbn:de:0030-drops-243894},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.23},
  annote =	{Keywords: sum-of-radii clustering, mergeable constraints, approximation algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.23
On the Instance Optimality of Detecting Collisions and Subgraphs

Authors: Omri Ben-Eliezer, Tomer Grossman, and Moni Naor

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Suppose you are given a function f: [n] → [n] via (black-box) query access to the function. You are looking to find something local, like a collision (a pair x ≠ y s.t. f(x) = f(y)). The question is whether knowing the "shape" of the function helps you or not (by shape we mean that some permutation of the function is known). Formally, we investigate the unlabeled instance optimality of substructure detection problems in graphs and functions. A problem is g(n)-instance optimal if it admits an algorithm A satisfying that for any possible input, the (randomized) query complexity of A is at most g(n) times larger than the query complexity of any algorithm A' which solves the same problem while holding an unlabeled copy of the input (i.e., any A' that "knows the structure of the input"). Our results point to a trichotomy of unlabeled instance optimality among substructure detection problems in graphs and functions: - A few very simple properties have an O(1)-instance optimal algorithm. - Most properties of graphs and functions, with examples such as containing a fixed point or a 3-collision in functions, or a triangle in graphs, are n^{c}-far from instance optimal for some constant c > 0. - The problems of collision detection in functions and finding a claw in a graph serve as a middle ground between the two regimes. We show that these two properties are not Ω(log n)-instance optimal, and conjecture that this bound is tight. We provide evidence towards this conjecture, by proving that finding a claw in a graph is O(log(n))-instance optimal among all input graphs for which the query complexity of an algorithm holding an unlabeled certificate is O(√{n/(log n)}).
Cite as

Omri Ben-Eliezer, Tomer Grossman, and Moni Naor. On the Instance Optimality of Detecting Collisions and Subgraphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ICALP.2025.23,
  author =	{Ben-Eliezer, Omri and Grossman, Tomer and Naor, Moni},
  title =	{{On the Instance Optimality of Detecting Collisions and Subgraphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.23},
  URN =		{urn:nbn:de:0030-drops-234002},
  doi =		{10.4230/LIPIcs.ICALP.2025.23},
  annote =	{Keywords: instance optimality, instance complexity, unlabeled certificate, subgraph detection, collision detection}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.79
Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries

Authors: Maxime Flin and Magnús M. Halldórsson

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider the problem of maintaining a proper (Δ + 1)-vertex coloring in a graph on n-vertices and maximum degree Δ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time Õ(n^{2/3}) against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent Õ(n^{8/9})-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic (Δ+1)-coloring algorithms. The main improvements are on the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms.
Cite as

Maxime Flin and Magnús M. Halldórsson. Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 79:1-79:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{flin_et_al:LIPIcs.ICALP.2025.79,
  author =	{Flin, Maxime and Halld\'{o}rsson, Magn\'{u}s M.},
  title =	{{Faster Dynamic (\Delta+1)-Coloring Against Adaptive Adversaries}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{79:1--79:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.79},
  URN =		{urn:nbn:de:0030-drops-234560},
  doi =		{10.4230/LIPIcs.ICALP.2025.79},
  annote =	{Keywords: Dynamic Graph Algorithms, Coloring}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.117
Incremental Approximate Single-Source Shortest Paths with Predictions

Authors: Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing interest in leveraging predictions for designing data structures with improved beyond-worst-case running times. In this paper, we study the fundamental data structure problem of maintaining approximate shortest paths in incremental graphs in the algorithms-with-predictions model. Given a sequence σ of edges that are inserted one at a time, the goal is to maintain approximate shortest paths from the source to each vertex in the graph at each time step. Before any edges arrive, the data structure is given a prediction of the online edge sequence σ̂ which is used to "warm start" its state. As our main result, we design a learned algorithm that maintains (1+ε)-approximate single-source shortest paths, which runs in Õ(m η log W/ε) time, where W is the weight of the heaviest edge and η is the prediction error. We show these techniques immediately extend to the all-pairs shortest-path setting as well. Our algorithms are consistent (performing nearly as fast as the offline algorithm) when predictions are nearly perfect, have a smooth degradation in performance with respect to the prediction error and, in the worst case, match the best offline algorithm up to logarithmic factors. That is, the algorithms are "ideal" in the algorithms-with-predictions model. As a building block, we study the offline incremental approximate single-source shortest-path (SSSP) problem. In the offline incremental SSSP problem, the edge sequence σ is known a priori and the goal is to construct a data structure that can efficiently return the length of the shortest paths in the intermediate graph G_t consisting of the first t edges, for all t. Note that the offline incremental problem is defined in the worst-case setting (without predictions) and is of independent interest.
Cite as

Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh. Incremental Approximate Single-Source Shortest Paths with Predictions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 117:1-117:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mccauley_et_al:LIPIcs.ICALP.2025.117,
  author =	{McCauley, Samuel and Moseley, Benjamin and Niaparast, Aidin and Niaparast, Helia and Singh, Shikha},
  title =	{{Incremental Approximate Single-Source Shortest Paths with Predictions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{117:1--117:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.117},
  URN =		{urn:nbn:de:0030-drops-234946},
  doi =		{10.4230/LIPIcs.ICALP.2025.117},
  annote =	{Keywords: Algorithms with Predictions, Shortest Paths, Approximation Algorithms, Dynamic Graph Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.14
Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments

Authors: Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, and Adarsh Srinivasan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given a k-CNF formula and an integer s ≥ 2, we study algorithms that obtain s solutions to the formula that are as dispersed as possible. For s = 2, this problem of computing the diameter of a k-CNF formula was initiated by Creszenzi and Rossi, who showed strong hardness results even for k = 2. The current best upper bound [Angelsmark and Thapper '04] goes to 4ⁿ as k → ∞. As our first result, we show that this quadratic blow up is not necessary by utilizing the Fast-Fourier transform (FFT) to give a O^*(2ⁿ) time exact algorithm for computing the diameter of any k-CNF formula. For s > 2, the problem was raised in the SAT community (Nadel '11) and several heuristics have been proposed for it, but no algorithms with theoretical guarantees are known. We give exact algorithms using FFT and clique-finding that run in O^*(2^{(s-1)n}) and O^*(s² |Ω_{𝐅}|^{ω ⌈ s/3 ⌉}) respectively, where |Ω_{𝐅}| is the size of the solutions space of the formula 𝐅 and ω is the matrix multiplication exponent. However, current SAT algorithms for finding one solution run in time O^*(2^{ε_{k}n}) for ε_{k} ≈ 1-Θ(1/k), which is much faster than all above run times. As our main result, we analyze two popular SAT algorithms - PPZ (Paturi, Pudlák, Zane '97) and Schöning’s ('02) algorithms, and show that in time poly(s)O^*(2^{ε_{k}n}), they can be used to approximate diameter as well as the dispersion (s > 2) problem. While we need to modify Schöning’s original algorithm for technical reasons, we show that the PPZ algorithm, without any modification, samples solutions in a geometric sense. We believe this geometric sampling property of PPZ may be of independent interest. Finally, we focus on diverse solutions to NP-complete optimization problems, and give bi-approximations running in time poly(s)O^*(2^{ε n}) with ε < 1 for several problems such as Maximum Independent Set, Minimum Vertex Cover, Minimum Hitting Set, Feedback Vertex Set, Multicut on Trees and Interval Vertex Deletion. For all of these problems, all existing exact methods for finding optimal diverse solutions have a runtime with at least an exponential dependence on the number of solutions s. Our methods show that by relaxing to bi-approximations, this dependence on s can be made polynomial.
Cite as

Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, and Adarsh Srinivasan. Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.ICALP.2025.14,
  author =	{Austrin, Per and Bercea, Ioana O. and Goswami, Mayank and Limaye, Nutan and Srinivasan, Adarsh},
  title =	{{Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.14},
  URN =		{urn:nbn:de:0030-drops-233916},
  doi =		{10.4230/LIPIcs.ICALP.2025.14},
  annote =	{Keywords: Exponential time algorithms, Satisfiability, k-SAT, PPZ, Sch\"{o}ning, Dispersion, Diversity}
}
  • Refine by Type
  • 19 Document/PDF
  • 15 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 10 2025
  • 2 2024
  • 1 2020
  • 1 2019

  • Refine by Author
  • 5 Bercea, Ioana O.
  • 2 Bandyapadhyay, Sayan
  • 2 Chen, Tianzhi
  • 2 Schmidt, Melanie
  • 1 Abrahamsen, Mikkel
  • Show More...

  • Refine by Series/Journal
  • 19 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Approximation algorithms analysis
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Data structures design and analysis
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Facility location and clustering
  • Show More...

  • Refine by Keyword
  • 3 TSP
  • 3 online algorithm
  • 3 sorting
  • 2 Dynamic Graph Algorithms
  • 2 approximation algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact