DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.13

Optimal Online Bipartite Matching in Degree-2 Graphs

Authors: Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.

Cite as

Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha. Optimal Online Bipartite Matching in Degree-2 Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ISAAC.2025.13,
  author =	{Bhangale, Amey and Chakraborty, Arghya and Harsha, Prahladh},
  title =	{{Optimal Online Bipartite Matching in Degree-2 Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.13},
  URN =		{urn:nbn:de:0030-drops-249216},
  doi =		{10.4230/LIPIcs.ISAAC.2025.13},
  annote =	{Keywords: Online Algorithm, Bipartite matching}
}

Document

DOI: 10.4230/LIPIcs.ITC.2025.4

Time-Space Tradeoffs of Truncation with Preprocessing

Authors: Krzysztof Pietrzak and Pengxiang Wang

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract

Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [Foteini Baldimtsi et al., 2022]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected 2^k different inputs one will find an output that starts with k zeros. Using such truncation one can for example save substantial gas fees on Blockchains where storing values is very expensive. While [Foteini Baldimtsi et al., 2022] show that truncation preserves the security of the underlying primitive, they only consider a setting without preprocessing. In this work we show that lower bounds on the time-space tradeoff for inverting random functions and permutations also hold with truncation, except for parameters ranges where the bound fails to hold for "trivial" reasons. Concretely, it’s known that any algorithm that inverts a random function or permutation with range N making T queries and using S bits of auxiliary input must satisfy S⋅ T ≥ Nlog N. This lower bound no longer holds in the truncated setting where one must only invert a challenge from a range of size N/2^k, as now one can simply save the replies to all N/2^k challenges, which requires S = log N⋅ N /2^k bits and allows to invert with T = 1 query. We show that with truncation, whenever S is somewhat smaller than the log N⋅ N /2^k bits required to store the entire truncated function table, the known S⋅ T ≥ Nlog N lower bound applies.

Cite as

Krzysztof Pietrzak and Pengxiang Wang. Time-Space Tradeoffs of Truncation with Preprocessing. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 4:1-4:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pietrzak_et_al:LIPIcs.ITC.2025.4,
  author =	{Pietrzak, Krzysztof and Wang, Pengxiang},
  title =	{{Time-Space Tradeoffs of Truncation with Preprocessing}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{4:1--4:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.4},
  URN =		{urn:nbn:de:0030-drops-243544},
  doi =		{10.4230/LIPIcs.ITC.2025.4},
  annote =	{Keywords: Time-Space Lower Bounds, Blockchains}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2025.93

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity

Authors: Jingyang Zhao and Mingyu Xiao

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider k-CVRP in general metrics and on general graphs, where k is the vehicle capacity. All three versions are APX-hard for any fixed k ≥ 3. Assume that the approximation ratio of metric TSP is 3/2. We present a (5/2 - Θ(√{1/k}))-approximation algorithm for the splittable and unit-demand cases, and a (5/2 + ln 2 - Θ(√{1/k}))-approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when k is less than a sufficiently large value, approximately 1.7 x 10⁷. For small values of k, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from 1.792 to 1.500 for k = 3, and from 1.750 to 1.500 for k = 4. For the unsplittable case, we improve the approximation ratio from 1.792 to 1.500 for k = 3, from 2.051 to 1.750 for k = 4, and from 2.249 to 2.157 for k = 5. The approximation ratio for k = 3 surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP - an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.

Cite as

Jingyang Zhao and Mingyu Xiao. Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhao_et_al:LIPIcs.MFCS.2025.93,
  author =	{Zhao, Jingyang and Xiao, Mingyu},
  title =	{{Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{93:1--93:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-242008},
  doi =		{10.4230/LIPIcs.MFCS.2025.93},
  annote =	{Keywords: Combinatorial Optimization, Capacitated Vehicle Routing, Approximation Algorithms, Graph Algorithms}
}

Document

DOI: 10.4230/LIPIcs.WABI.2025.10

DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs

Authors: Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract

Determining the distance between two loci within a genomic region is a recurrent operation in various tasks in computational genomics. A notable example of this task arises in paired-end read mapping as a form of validation of distances between multiple alignments. While straightforward for a single genome, graph-based reference structures render the operation considerably more involved. Given the sheer number of such queries in a typical read mapping experiment, an efficient algorithm for answering distance queries is crucial. In this paper, we introduce DiVerG, a compact data structure as well as a fast and scalable algorithm, for constructing distance indexes for general sequence graphs on multi-core CPU and many-core GPU architectures. DiVerG is based on PairG [Jain et al., 2019], but overcomes the limitations of PairG by exploiting the extensive potential for improvements in terms of scalability and space efficiency. As a consequence, DiVerG can process substantially larger datasets, such as whole human genomes, which are unmanageable by PairG. DiVerG offers faster index construction time and consistently faster query time with gains proportional to the size of the underlying compact data structure. We demonstrate that our method performs favorably on multiple real datasets at various scales. DiVerG achieves superior performance over PairG; e.g. resulting to 2.5-4x speed-up in query time, 44-340x smaller index size, and 3-50x faster construction time for the genome graph of the MHC region, as a particularly variable region of the human genome. The implementation is available at: https://github.com/cartoonist/diverg

Cite as

Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall. DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghaffaari_et_al:LIPIcs.WABI.2025.10,
  author =	{Ghaffaari, Ali and Sch\"{o}nhuth, Alexander and Marschall, Tobias},
  title =	{{DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.10},
  URN =		{urn:nbn:de:0030-drops-239369},
  doi =		{10.4230/LIPIcs.WABI.2025.10},
  annote =	{Keywords: Sequence graph, distance index, read mapping, sparse matrix}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.48

Improved Streaming Edge Coloring

Authors: Shiri Chechik, Hongyi Chen, and Tianyi Zhang

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

Abstract

Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains n vertices and has maximum vertex degree Δ, it is known that in the W-streaming model, an O(Δ²)-edge coloring can be computed deterministically with Õ(n) space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an O(Δ^{1.5})-edge coloring can be computed by a Õ(n)-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to Õ(Δ^{4/3+ε}) using space Õ(n) deterministically, for any constant ε > 0. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.

Cite as

Shiri Chechik, Hongyi Chen, and Tianyi Zhang. Improved Streaming Edge Coloring. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chechik_et_al:LIPIcs.ICALP.2025.48,
  author =	{Chechik, Shiri and Chen, Hongyi and Zhang, Tianyi},
  title =	{{Improved Streaming Edge Coloring}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{48:1--48:18},
  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.48},
  URN =		{urn:nbn:de:0030-drops-234257},
  doi =		{10.4230/LIPIcs.ICALP.2025.48},
  annote =	{Keywords: edge coloring, streaming}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.110

An Optimal 3-Fault-Tolerant Connectivity Oracle

Authors: Evangelos Kosinas

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

Abstract

We present an optimal oracle for answering connectivity queries in undirected graphs in the presence of at most three vertex failures. Specifically, we show that we can process a graph G in O(n+m) time, in order to build a data structure that occupies O(n) space, which can be used in order to answer queries of the form "given a set F of at most three vertices, and two vertices x and y not in F, are x and y connected in G⧵ F?" in constant time, where n and m denote the number of vertices and edges, respectively, of G. The idea is to rely on the DFS-based framework introduced by Kosinas [ESA'23], for handling connectivity queries in the presence of multiple vertex failures. Our technical contribution is to show how to appropriately extend the toolkit of the DFS-based parameters, in order to optimally handle up to three vertex failures. Our approach has the interesting property that it does not rely on a compact representation of vertex cuts, and has the potential to provide optimal solutions for more vertex failures. Furthermore, we show that the DFS-based framework can be easily extended in order to answer vertex-cut queries, and the number of connected components in the presence of multiple vertex failures. In the case of three vertex failures, we can answer such queries in O(log n) time.

Cite as

Evangelos Kosinas. An Optimal 3-Fault-Tolerant Connectivity Oracle. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 110:1-110:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kosinas:LIPIcs.ICALP.2025.110,
  author =	{Kosinas, Evangelos},
  title =	{{An Optimal 3-Fault-Tolerant Connectivity Oracle}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{110:1--110: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.110},
  URN =		{urn:nbn:de:0030-drops-234879},
  doi =		{10.4230/LIPIcs.ICALP.2025.110},
  annote =	{Keywords: Graphs, Connectivity, Fault-Tolerant, Oracles}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.5

Acceleration Meets Inverse Maintenance: Faster 𝓁_∞-Regression

Authors: Deeksha Adil, Shunhua Jiang, and Rasmus Kyng

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

Abstract

We propose a randomized multiplicative weight update (MWU) algorithm for 𝓁_{∞} regression that runs in Õ(n^{2+1/22.5} poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/18} polylog(1/ε)) runtime in the low-accuracy regime. Our algorithm combines state-of-the-art inverse maintenance data structures with acceleration. In order to do so, we propose a novel acceleration scheme for MWU that exhibits stability and robustness, which are required for the efficient implementations of the inverse maintenance data structures. We also design a faster deterministic MWU algorithm that runs in Õ(n^{2+1/12}poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/6} poly log(1/ε)) runtime in the low-accuracy regime. We achieve this by showing a novel stability result that goes beyond previously known works based on interior point methods (IPMs). Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible.

Cite as

Deeksha Adil, Shunhua Jiang, and Rasmus Kyng. Acceleration Meets Inverse Maintenance: Faster 𝓁_∞-Regression. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adil_et_al:LIPIcs.ICALP.2025.5,
  author =	{Adil, Deeksha and Jiang, Shunhua and Kyng, Rasmus},
  title =	{{Acceleration Meets Inverse Maintenance: Faster 𝓁\underline∞-Regression}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{5:1--5:16},
  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.5},
  URN =		{urn:nbn:de:0030-drops-233823},
  doi =		{10.4230/LIPIcs.ICALP.2025.5},
  annote =	{Keywords: Regression, Inverse Maintenance, Multiplicative Weights Update}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.15

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in ℝ^d (d ≥ 1), or equivalently, distance spaces that can be isometrically embedded in ℝ^d. In this work, we investigate whether a distance space can be isometrically embedded in ℝ^d after applying a limited number of modifications. Specifically, we focus on two types of modifications: outlier deletion (removing points) and distance modification (adjusting distances between points). The central problem, Euclidean Embedding Editing, asks whether an input distance space on n points can be transformed, using at most k modifications, into a space that is isometrically embeddable in ℝ^d. We present several fixed-parameter tractable (FPT) and approximation algorithms for this problem. Our first result is an algorithm that solves Euclidean Embedding Editing in time (dk)^𝒪(d+k) + n^𝒪(1). The core subroutine of this algorithm, which is of independent interest, is a polynomial-time method for compressing the input distance space into an equivalent instance of Euclidean Embedding Editing with 𝒪((dk)²) points. For the special but important case of Euclidean Embedding Editing where only outlier deletions are allowed, we improve the parameter dependence of the FPT algorithm and obtain a running time of min{(d+3)^k, 2^{d+k}} ⋅ n^𝒪(1). Additionally, we provide an FPT-approximation algorithm for this problem, which outputs a set of at most 2 ⋅ Opt outliers in time 2^d ⋅ n^{𝒪(1)}. This 2-approximation algorithm improves upon the previous (3+ε)-approximation algorithm by Sidiropoulos, Wang, and Wang [SODA '17]. Furthermore, we complement our algorithms with hardness results motivating our choice of parameterizations.

Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, and Saket Saurabh. When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.SoCG.2025.15,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.15},
  URN =		{urn:nbn:de:0030-drops-231672},
  doi =		{10.4230/LIPIcs.SoCG.2025.15},
  annote =	{Keywords: Parameterized Complexity, Euclidean Embedding, FPT-approximation}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.49

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications

Authors: Arnold Filtser

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

Given a metric space (X,d_X), a (β,s,Δ)-sparse cover is a collection of clusters 𝒞 ⊆ P(X) with diameter at most Δ, such that for every point x ∈ X, the ball B_X(x,Δ/β) is fully contained in some cluster C ∈ 𝒞, and x belongs to at most s clusters in 𝒞. Our main contribution is to show that the shortest path metric of every K_r-minor free graphs admits (O(r),O(r²),Δ)-sparse cover, and for every ε > 0, (4+ε,O(1/ε)^r,Δ)-sparse cover (for arbitrary Δ > 0). We then use this sparse cover to show that every K_r-minor free graph embeds into 𝓁_∞^{Õ(1/ε)^{r+1}⋅log n} with distortion 3+ε (resp. into 𝓁_∞^{Õ(r²)⋅log n} with distortion O(r)). Further, among other applications, this sparse cover immediately implies an algorithm for the oblivious buy-at-bulk problem in fixed minor free graphs with the tight approximation factor O(log n) (previously nothing beyond general graphs was known).

Cite as

Arnold Filtser. On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{filtser:LIPIcs.SoCG.2025.49,
  author =	{Filtser, Arnold},
  title =	{{On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.49},
  URN =		{urn:nbn:de:0030-drops-232015},
  doi =		{10.4230/LIPIcs.SoCG.2025.49},
  annote =	{Keywords: Sparse cover, minor free graphs, metric embeddings, 𝓁\underline∞, oblivious buy-at-bulk}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.72

Geometric Bipartite Matching Based Exact Algorithms for Server Problems

Authors: Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

For any given metric space, obtaining an offline optimal solution to the classical k-server problem can be reduced to solving a minimum-cost partial bipartite matching between two point sets A and B within that metric space. For d-dimensional 𝓁_p metric space, we present an Õ(min{nk, n^{2-1/(2d+1)}log Δ}⋅ Φ(n)) time algorithm for solving this instance of minimum-cost partial bipartite matching; here, Δ represents the spread of the point set, and Φ(n) is the query/update time of a d-dimensional dynamic weighted nearest neighbor data structure. Our algorithm improves upon prior algorithms that require at least Ω(nkΦ(n)) time. The design of minimum-cost (partial) bipartite matching algorithms that make sub-quadratic queries to a weighted nearest-neighbor data structure, even for bounded spread instances, is a major open problem in computational geometry. We resolve this problem at least for the instances that are generated by the offline version of the k-server problem. Our algorithm employs a hierarchical partitioning approach, dividing the points of A∪ B into rectangles. It maintains a partial minimum-cost matching where any point b ∈ B is either matched to another point a ∈ A or to the boundary of the rectangle it is located in. The algorithm involves iteratively merging pairs of rectangles by erasing the shared boundary between them and recomputing the minimum-cost partial matching. This continues until all boundaries are erased and we obtain the desired minimum-cost partial matching of A and B. We exploit geometry in our analysis to show that each point participates in only Õ(n^{1-1/(2d+1)}log Δ) number of augmenting paths, leading to a total execution time of Õ(n^{2-1/(2d+1)}Φ(n)log Δ). We also show that, for the 𝓁₁ norm and d dimensions, any algorithm that can solve instances of the offline n-server problem with an exponential spread in T(n) time can be used to compute minimum-cost bipartite matching in a complete graph defined on two (d-1)-dimensional point sets under the 𝓁₁ norm within T(n) time. This suggests that removing spread from the execution time of our algorithm may be difficult as it immediately results in a sub-quadratic algorithm for bipartite matching under the 𝓁₁ norm.

Cite as

Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle. Geometric Bipartite Matching Based Exact Algorithms for Server Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{raghvendra_et_al:LIPIcs.SoCG.2025.72,
  author =	{Raghvendra, Sharath and Shirzadian, Pouyan and Sowle, Rachita},
  title =	{{Geometric Bipartite Matching Based Exact Algorithms for Server Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{72:1--72:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.72},
  URN =		{urn:nbn:de:0030-drops-232240},
  doi =		{10.4230/LIPIcs.SoCG.2025.72},
  annote =	{Keywords: Minimum-Cost Bipartite Matching, Server Problems, Primal-Dual Approach}
}

Document

DOI: 10.4230/LIPIcs.SAND.2025.4

On b-Matching and Fully-Dynamic Maximum k-Edge Coloring

Authors: Antoine El-Hayek, Kathrin Hanauer, and Monika Henzinger

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract

Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. We present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant. Using these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor.

Cite as

Antoine El-Hayek, Kathrin Hanauer, and Monika Henzinger. On b-Matching and Fully-Dynamic Maximum k-Edge Coloring. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{elhayek_et_al:LIPIcs.SAND.2025.4,
  author =	{El-Hayek, Antoine and Hanauer, Kathrin and Henzinger, Monika},
  title =	{{On b-Matching and Fully-Dynamic Maximum k-Edge Coloring}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.4},
  URN =		{urn:nbn:de:0030-drops-230571},
  doi =		{10.4230/LIPIcs.SAND.2025.4},
  annote =	{Keywords: dynamic algorithm, graph algorithm, matching, b-matching, edge coloring}
}

Document

Vision

DOI: 10.4230/TGDK.1.1.8

Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges

Authors: Claudia d'Amato, Louis Mahon, Pierre Monnin, and Giorgos Stamou

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract

The graph model is nowadays largely adopted to model a wide range of knowledge and data, spanning from social networks to knowledge graphs (KGs), representing a successful paradigm of how symbolic and transparent AI can scale on the World Wide Web. However, due to their unprecedented volume, they are generally tackled by Machine Learning (ML) and mostly numeric based methods such as graph embedding models (KGE) and deep neural networks (DNNs). The latter methods have been proved lately very efficient, leading the current AI spring. In this vision paper, we introduce some of the main existing methods for combining KGs and ML, divided into two categories: those using ML to improve KGs, and those using KGs to improve results on ML tasks. From this introduction, we highlight research gaps and perspectives that we deem promising and currently under-explored for the involved research communities, spanning from KG support for LLM prompting, integration of KG semantics in ML models to symbol-based methods, interpretability of ML models, and the need for improved benchmark datasets. In our opinion, such perspectives are stepping stones in an ultimate view of KGs as central assets for neuro-symbolic and explainable AI.

Cite as

Claudia d'Amato, Louis Mahon, Pierre Monnin, and Giorgos Stamou. Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 8:1-8:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{damato_et_al:TGDK.1.1.8,
  author =	{d'Amato, Claudia and Mahon, Louis and Monnin, Pierre and Stamou, Giorgos},
  title =	{{Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{8:1--8:35},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.8},
  URN =		{urn:nbn:de:0030-drops-194824},
  doi =		{10.4230/TGDK.1.1.8},
  annote =	{Keywords: Graph-based Learning, Knowledge Graph Embeddings, Large Language Models, Explainable AI, Knowledge Graph Completion \& Curation}
}

Document

Vision

DOI: 10.4230/TGDK.1.1.9

Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination

Authors: Luis-Daniel Ibáñez, John Domingue, Sabrina Kirrane, Oshani Seneviratne, Aisling Third, and Maria-Esther Vidal

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract

Knowledge Graphs (KGs) have emerged as fundamental platforms for powering intelligent decision-making and a wide range of Artificial Intelligence (AI) services across major corporations such as Google, Walmart, and AirBnb. KGs complement Machine Learning (ML) algorithms by providing data context and semantics, thereby enabling further inference and question-answering capabilities. The integration of KGs with neuronal learning (e.g., Large Language Models (LLMs)) is currently a topic of active research, commonly named neuro-symbolic AI. Despite the numerous benefits that can be accomplished with KG-based AI, its growing ubiquity within online services may result in the loss of self-determination for citizens as a fundamental societal issue. The more we rely on these technologies, which are often centralised, the less citizens will be able to determine their own destinies. To counter this threat, AI regulation, such as the European Union (EU) AI Act, is being proposed in certain regions. The regulation sets what technologists need to do, leading to questions concerning How the output of AI systems can be trusted? What is needed to ensure that the data fuelling and the inner workings of these artefacts are transparent? How can AI be made accountable for its decision-making? This paper conceptualises the foundational topics and research pillars to support KG-based AI for self-determination. Drawing upon this conceptual framework, challenges and opportunities for citizen self-determination are illustrated and analysed in a real-world scenario. As a result, we propose a research agenda aimed at accomplishing the recommended objectives.

Cite as

Luis-Daniel Ibáñez, John Domingue, Sabrina Kirrane, Oshani Seneviratne, Aisling Third, and Maria-Esther Vidal. Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 9:1-9:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{ibanez_et_al:TGDK.1.1.9,
  author =	{Ib\'{a}\~{n}ez, Luis-Daniel and Domingue, John and Kirrane, Sabrina and Seneviratne, Oshani and Third, Aisling and Vidal, Maria-Esther},
  title =	{{Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{9:1--9:32},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.9},
  URN =		{urn:nbn:de:0030-drops-194839},
  doi =		{10.4230/TGDK.1.1.9},
  annote =	{Keywords: Trust, Accountability, Autonomy, AI, Knowledge Graphs}
}

Document

Position

DOI: 10.4230/TGDK.1.1.5

Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities

Authors: Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract

The term life sciences refers to the disciplines that study living organisms and life processes, and include chemistry, biology, medicine, and a range of other related disciplines. Research efforts in life sciences are heavily data-driven, as they produce and consume vast amounts of scientific data, much of which is intrinsically relational and graph-structured. The volume of data and the complexity of scientific concepts and relations referred to therein promote the application of advanced knowledge-driven technologies for managing and interpreting data, with the ultimate aim to advance scientific discovery. In this survey and position paper, we discuss recent developments and advances in the use of graph-based technologies in life sciences and set out a vision for how these technologies will impact these fields into the future. We focus on three broad topics: the construction and management of Knowledge Graphs (KGs), the use of KGs and associated technologies in the discovery of new knowledge, and the use of KGs in artificial intelligence applications to support explanations (explainable AI). We select a few exemplary use cases for each topic, discuss the challenges and open research questions within these topics, and conclude with a perspective and outlook that summarizes the overarching challenges and their potential solutions as a guide for future research.

Cite as

Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma. Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 5:1-5:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{chen_et_al:TGDK.1.1.5,
  author =	{Chen, Jiaoyan and Dong, Hang and Hastings, Janna and Jim\'{e}nez-Ruiz, Ernesto and L\'{o}pez, Vanessa and Monnin, Pierre and Pesquita, Catia and \v{S}koda, Petr and Tamma, Valentina},
  title =	{{Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:33},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.5},
  URN =		{urn:nbn:de:0030-drops-194791},
  doi =		{10.4230/TGDK.1.1.5},
  annote =	{Keywords: Knowledge graphs, Life science, Knowledge discovery, Explainable AI}
}

Document

DOI: 10.4230/DagSemProc.09291.22

Notes from the Discussion Group on "Evaluation"

Authors: David Brown

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)

Abstract

Group Members: Harold Cohen, Maggie Boden, Dave Brown, Paul Brown, Oliver Deussen, Philip Galanter. These notes represent approximately what was discussed by the group members over a period of several hours over two days. There has been some attempt to organize the material, but little attempt to expand it to make it coherent—we rambled, so do the notes. The notes, and this report, were recorded, organized, and elaborated into this form by Dave Brown.

Cite as

David Brown. Notes from the Discussion Group on "Evaluation". In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brown:DagSemProc.09291.22,
  author =	{Brown, David},
  title =	{{Notes from the Discussion Group on "Evaluation"}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.22},
  URN =		{urn:nbn:de:0030-drops-22128},
  doi =		{10.4230/DagSemProc.09291.22},
  annote =	{Keywords: Evaluation, art, artistic, creativity}
}

16 Search Results for "Cohen, Harold"

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