6 Search Results for "Leo, Kevin"

Document
DOI: 10.4230/LIPIcs.SEA.2024.5
Buffered Streaming Edge Partitioning

Authors: Adil Chhabra, Marcelo Fonseca Faraj, Christian Schulz, and Daniel Seemaier

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Addressing the challenges of processing massive graphs, which are prevalent in diverse fields such as social, biological, and technical networks, we introduce HeiStreamE and FreightE, two innovative (buffered) streaming algorithms designed for efficient edge partitioning of large-scale graphs. HeiStreamE utilizes an adapted Split-and-Connect graph model and a Fennel-based multilevel partitioning scheme, while FreightE partitions a hypergraph representation of the input graph. Besides ensuring superior solution quality, these approaches also overcome the limitations of existing algorithms by maintaining linear dependency on the graph size in both time and memory complexity with no dependence on the number of blocks of partition. Our comprehensive experimental analysis demonstrates that HeiStreamE outperforms current streaming algorithms and the re-streaming algorithm 2PS in partitioning quality (replication factor), and is more memory-efficient for real-world networks where the number of edges is far greater than the number of vertices. Further, FreightE is shown to produce fast and efficient partitions, particularly for higher numbers of partition blocks.
Cite as

Adil Chhabra, Marcelo Fonseca Faraj, Christian Schulz, and Daniel Seemaier. Buffered Streaming Edge Partitioning. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chhabra_et_al:LIPIcs.SEA.2024.5,
  author =	{Chhabra, Adil and Fonseca Faraj, Marcelo and Schulz, Christian and Seemaier, Daniel},
  title =	{{Buffered Streaming Edge Partitioning}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.5},
  URN =		{urn:nbn:de:0030-drops-203701},
  doi =		{10.4230/LIPIcs.SEA.2024.5},
  annote =	{Keywords: graph partitioning, edge partitioning, streaming, online, buffered partitioning}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.15
Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs

Authors: Daniel Hambly, Rhyd Lewis, and Padraig Corcoran

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
In this paper, we examine the NP-hard problem of identifying fixed-length s-t paths in edge-weighted graphs - that is, a path of a desired length k from a source vertex s to a target vertex t. Many existing strategies look at paths whose lengths are determined by the number of edges in the path. We, however, look at the length of the path as the sum of the edge weights. Here, three exact algorithms for this problem are proposed: the first based on an integer programming (IP) formulation, the second a backtracking algorithm, and the third based on an extension of Yen’s algorithm. Analysis of these algorithms on random graphs shows that the backtracking algorithm performs best on smaller values of k, whilst the IP is preferable for larger values of k.
Cite as

Daniel Hambly, Rhyd Lewis, and Padraig Corcoran. Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 15:1-15:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hambly_et_al:LIPIcs.SEA.2024.15,
  author =	{Hambly, Daniel and Lewis, Rhyd and Corcoran, Padraig},
  title =	{{Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{15:1--15:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.15},
  URN =		{urn:nbn:de:0030-drops-203805},
  doi =		{10.4230/LIPIcs.SEA.2024.15},
  annote =	{Keywords: Graphs, paths, backtracking, integer programming, Yen’s algorithm}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.19
Algorithms for Gradual Polyline Simplification

Authors: Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Displaying line data is important in many visualization applications, and especially in the context of interactive geographical and cartographic visualization. When rendering linear features as roads, rivers or movement data on zoomable maps, the challenge is to display the data in an appropriate level of detail. A too detailed representation results in slow rendering and cluttered maps, while a too coarse representation might miss important data aspects. In this paper, we propose the gradual line simplification (GLS) problem, which aims to compute a fine-grained succession of consistent simplifications of a given input polyline with certain quality guarantees. The core concept of gradual simplification is to iteratively remove points from the polyline to obtain increasingly coarser representations. We devise two objective functions to guide this simplification process and present dynamic programs that compute the optimal solutions in 𝒪(n³) for an input line with n points. For practical application to large inputs, we also devise significantly faster greedy algorithms that provide constant factor guarantees for both problem variants at once. In an extensive experimental study on real-world data, we demonstrate that our algorithms are capable of producing simplification sequences of high quality within milliseconds on polylines consisting of over half a million points.
Cite as

Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt. Algorithms for Gradual Polyline Simplification. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{krumbholz_et_al:LIPIcs.SEA.2024.19,
  author =	{Krumbholz, Nick and Funke, Stefan and Sch\"{a}fer, Peter and Storandt, Sabine},
  title =	{{Algorithms for Gradual Polyline Simplification}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.19},
  URN =		{urn:nbn:de:0030-drops-203847},
  doi =		{10.4230/LIPIcs.SEA.2024.19},
  annote =	{Keywords: Polyline simplification, Progressive simplification, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.22
Efficient Computation of Topological Integral Transforms

Authors: Vadim Lebovici, Steve Oudot, and Hugo Passe

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Topological integral transforms have found many applications in shape analysis, from prediction of clinical outcomes in brain cancer to analysis of barley seeds. Using Euler characteristic as a measure, these objects record rich geometric information on weighted polytopal complexes. While some implementations exist, they only enable discretized representations of the transforms, and they do not handle weighted complexes (such as for instance images). Moreover, recent hybrid transforms lack an implementation. In this paper, we introduce eucalc, a novel implementation of three topological integral transforms - the Euler characteristic transform, the Radon transform, and hybrid transforms - for weighted cubical complexes. Leveraging piecewise linear Morse theory and Euler calculus, the algorithms significantly reduce computational complexity by focusing on critical points. Our software provides exact representations of transforms, handles both binary and grayscale images, and supports multi-core processing. It is publicly available as a C++ library with a Python wrapper. We present mathematical foundations, implementation details, and experimental evaluations, demonstrating eucalc’s efficiency.
Cite as

Vadim Lebovici, Steve Oudot, and Hugo Passe. Efficient Computation of Topological Integral Transforms. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lebovici_et_al:LIPIcs.SEA.2024.22,
  author =	{Lebovici, Vadim and Oudot, Steve and Passe, Hugo},
  title =	{{Efficient Computation of Topological Integral Transforms}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.22},
  URN =		{urn:nbn:de:0030-drops-203878},
  doi =		{10.4230/LIPIcs.SEA.2024.22},
  annote =	{Keywords: Topological data analysis, Euler calculus, Topological integral transform, Euler characteristic transform, Hybrid transforms}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.49
Human-Centred Feasibility Restoration

Authors: Ilankaikone Senthooran, Matthias Klapperstueck, Gleb Belov, Tobias Czauderna, Kevin Leo, Mark Wallace, Michael Wybrow, and Maria Garcia de la Banda

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Decision systems for solving real-world combinatorial problems must be able to report infeasibility in such a way that users can understand the reasons behind it, and understand how to modify the problem to restore feasibility. Current methods mainly focus on reporting one or more subsets of the problem constraints that cause infeasibility. Methods that also show users how to restore feasibility tend to be less flexible and/or problem-dependent. We describe a problem-independent approach to feasibility restoration that combines existing techniques from the literature in novel ways to yield meaningful, useful, practical and flexible user support. We evaluate the resulting framework on two real-world applications.
Cite as

Ilankaikone Senthooran, Matthias Klapperstueck, Gleb Belov, Tobias Czauderna, Kevin Leo, Mark Wallace, Michael Wybrow, and Maria Garcia de la Banda. Human-Centred Feasibility Restoration. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{senthooran_et_al:LIPIcs.CP.2021.49,
  author =	{Senthooran, Ilankaikone and Klapperstueck, Matthias and Belov, Gleb and Czauderna, Tobias and Leo, Kevin and Wallace, Mark and Wybrow, Michael and de la Banda, Maria Garcia},
  title =	{{Human-Centred Feasibility Restoration}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{49:1--49:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.49},
  URN =		{urn:nbn:de:0030-drops-153408},
  doi =		{10.4230/LIPIcs.CP.2021.49},
  annote =	{Keywords: Combinatorial optimisation, modelling, human-centred, conflict resolution, feasibility restoration, explainable AI, soft constraints}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.79
Dots & Polygons (Media Exposition)

Authors: Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We present a new game, Dots & Polygons, played on a planar point set. We prove that its NP-hard and discuss strategies for the case when the point set is in convex position.
Cite as

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten. Dots & Polygons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 79:1-79:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2020.79,
  author =	{Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max and Rensen, Jolan and van Schooten, Leo},
  title =	{{Dots \& Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{79:1--79:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.79},
  URN =		{urn:nbn:de:0030-drops-122371},
  doi =		{10.4230/LIPIcs.SoCG.2020.79},
  annote =	{Keywords: Dots \& Boxes, NP-hard, game, cycle packing}
}
  • Refine by Author
  • 1 Belov, Gleb
  • 1 Buchin, Kevin
  • 1 Chhabra, Adil
  • 1 Corcoran, Padraig
  • 1 Czauderna, Tobias
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Integer programming
  • 1 Information systems → Fixed length attributes
  • 1 Mathematics of computing → Algebraic topology
  • 1 Theory of computation → Backtracking
  • Show More...

  • Refine by Keyword
  • 1 Combinatorial optimisation
  • 1 Dots & Boxes
  • 1 Euler calculus
  • 1 Euler characteristic transform
  • 1 Fréchet distance
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 4 2024
  • 1 2020
  • 1 2021

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact