48 Search Results for "Schulz, Christian"


Volume

LIPIcs, Volume 233

20th International Symposium on Experimental Algorithms (SEA 2022)

SEA 2022, July 25-27, 2022, Heidelberg, Germany

Editors: Christian Schulz and Bora Uçar

Document
Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)

Authors: George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman

Published in: Dagstuhl Reports, Volume 13, Issue 8 (2024)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.

Cite as

George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331). In Dagstuhl Reports, Volume 13, Issue 8, pp. 1-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@Article{karypis_et_al:DagRep.13.8.1,
  author =	{Karypis, George and Schulz, Christian and Strash, Darren and Ajwani, Deepak and Bisseling, Rob H. and Casel, Katrin and \c{C}ataly\"{u}rek, \"{U}mit V. and Chevalier, C\'{e}dric and Chudigiewitsch, Florian and Faraj, Marcelo Fonseca and Fellows, Michael and Gottesb\"{u}ren, Lars and Heuer, Tobias and Kaya, Kamer and Lacki, Jakub and Langguth, Johannes and Li, Xiaoye Sherry and Mayer, Ruben and Meintrup, Johannes and Mizutani, Yosuke and Pellegrini, Fran\c{c}ois and Petrini, Fabrizio and Rosamond, Frances and Safro, Ilya and Schlag, Sebastian and Sharma, Roohani and Sullivan, Blair D. and U\c{c}ar, Bora and Yzelman, Albert-Jan},
  title =	{{Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)}},
  pages =	{1--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{8},
  editor =	{Karypis, George and Schulz, Christian and Strash, Darren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.8.1},
  URN =		{urn:nbn:de:0030-drops-198114},
  doi =		{10.4230/DagRep.13.8.1},
  annote =	{Keywords: combinatorial optimization, experimental algorithmics, parallel algorithms}
}
Document
Faster Local Motif Clustering via Maximum Flows

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

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
Local clustering aims to identify a cluster within a given graph that includes a designated seed node or a significant portion of a group of seed nodes. This cluster should be well-characterized, i.e., it has a high number of internal edges and a low number of external edges. In this work, we propose SOCIAL, a novel algorithm for local motif clustering which optimizes for motif conductance based on a local hypergraph model representation of the problem and an adapted version of the max-flow quotient-cut improvement algorithm (MQI). In our experiments with the triangle motif, SOCIAL produces local clusters with an average motif conductance 1.7% lower than the state-of-the-art, while being up to multiple orders of magnitude faster.

Cite as

Adil Chhabra, Marcelo Fonseca Faraj, and Christian Schulz. Faster Local Motif Clustering via Maximum Flows. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{chhabra_et_al:LIPIcs.ESA.2023.34,
  author =	{Chhabra, Adil and Fonseca Faraj, Marcelo and Schulz, Christian},
  title =	{{Faster Local Motif Clustering via Maximum Flows}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.34},
  URN =		{urn:nbn:de:0030-drops-186871},
  doi =		{10.4230/LIPIcs.ESA.2023.34},
  annote =	{Keywords: local motif clustering, motif conductance, maximum flows, max-flow quotient-cut improvement}
}
Document
FREIGHT: Fast Streaming Hypergraph Partitioning

Authors: Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)


Abstract
Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.

Cite as

Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz. FREIGHT: Fast Streaming Hypergraph Partitioning. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{eyubov_et_al:LIPIcs.SEA.2023.15,
  author =	{Eyubov, Kamal and Fonseca Faraj, Marcelo and Schulz, Christian},
  title =	{{FREIGHT: Fast Streaming Hypergraph Partitioning}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.15},
  URN =		{urn:nbn:de:0030-drops-183657},
  doi =		{10.4230/LIPIcs.SEA.2023.15},
  annote =	{Keywords: Hypergraph partitioning, graph partitioning, edge partitioning, streaming}
}
Document
Arc-Flags Meet Trip-Based Public Transit Routing

Authors: Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)


Abstract
We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compared to previous attempts to apply Arc-Flags to public transit networks, which saw limited success, our approach uses stronger pruning rules to reduce the search space. Our experiments show that Arc-Flag TB achieves a speedup of up to two orders of magnitude over TB, offering query times of less than a millisecond even on large countrywide networks. Compared to the state-of-the-art speedup technique Trip-Based Public Transit Routing Using Condensed Search Trees (TB-CST), our algorithm achieves similar query times but requires significantly less additional memory. Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. In contrast, Arc-Flag TB offers a tradeoff between query performance and memory usage due to the fact that the number of regions in the network partition required by our algorithm is a configurable parameter. We also identify a previously undiscovered issue in the transfer precomputation of TB, which causes both TB-CST and Arc-Flag TB to answer some queries incorrectly. We provide discussion on how to resolve this issue in the future. Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks.

Cite as

Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil. Arc-Flags Meet Trip-Based Public Transit Routing. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.SEA.2023.16,
  author =	{Gro{\ss}mann, Ernestine and Sauer, Jonas and Schulz, Christian and Steil, Patrick},
  title =	{{Arc-Flags Meet Trip-Based Public Transit Routing}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.16},
  URN =		{urn:nbn:de:0030-drops-183664},
  doi =		{10.4230/LIPIcs.SEA.2023.16},
  annote =	{Keywords: Public transit routing, graph algorithms, algorithm engineering}
}
Document
Beyond the Threaded Programming Model on Real-Time Operating Systems

Authors: Erling Rennemo Jellum, Shaokai Lin, Peter Donovan, Efsane Soyer, Fuzail Shakir, Torleiv Bryne, Milica Orlandic, Marten Lohstroh, and Edward A. Lee

Published in: OASIcs, Volume 108, Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)


Abstract
The use of a real-time operating system (RTOS) raises the abstraction level for embedded systems design when compared to traditional bare-metal programming, resulting in simpler and more reusable application code. Modern RTOSes for resource-constrained platforms, like Zephyr and FreeRTOS, also offer threading support, but this kind of shared memory concurrency is a poor fit for expressing the reactive and interactive behaviors that are common in embedded systems. To address this, alternative concurrency models like the actor model or communicating sequential processes have been proposed. While those alternatives enable reactive design patterns, they fail to deliver determinism and do not address timing. This makes it difficult to verify that implemented behavior is as intended and impossible to specify timing constraints in a portable way. This makes it hard to create reusable library components out of common embedded design patterns, forcing developers to keep reinventing the wheel for each application and each platform. In this paper, we introduce the embedded target of Lingua Franca (LF) as a means to move beyond the threaded programming model provided by RTOSes and improve the state of the art in embedded programming. LF is based on the reactor model of computation, which is reactive, deterministic, and timed, providing a means to express concurrency and timing in a platform-independent way. We compare the performance of LF versus threaded C code - both running on Zephyr - in terms of response time, timing precision, throughput, and memory footprint.

Cite as

Erling Rennemo Jellum, Shaokai Lin, Peter Donovan, Efsane Soyer, Fuzail Shakir, Torleiv Bryne, Milica Orlandic, Marten Lohstroh, and Edward A. Lee. Beyond the Threaded Programming Model on Real-Time Operating Systems. In Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023). Open Access Series in Informatics (OASIcs), Volume 108, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{jellum_et_al:OASIcs.NG-RES.2023.3,
  author =	{Jellum, Erling Rennemo and Lin, Shaokai and Donovan, Peter and Soyer, Efsane and Shakir, Fuzail and Bryne, Torleiv and Orlandic, Milica and Lohstroh, Marten and Lee, Edward A.},
  title =	{{Beyond the Threaded Programming Model on Real-Time Operating Systems}},
  booktitle =	{Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)},
  pages =	{3:1--3:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-268-6},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{108},
  editor =	{Terraneo, Federico and Cattaneo, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2023.3},
  URN =		{urn:nbn:de:0030-drops-177348},
  doi =		{10.4230/OASIcs.NG-RES.2023.3},
  annote =	{Keywords: Real time, concurrency, reactors, Lingua Franca, RTOS}
}
Document
The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set

Authors: Ernestine Großmann, Tobias Heuer, Christian Schulz, and Darren Strash

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)


Abstract
The Parameterized Algorithms and Computational Experiments challenge (PACE) 2022 was devoted to engineer algorithms solving the NP-hard Directed Feedback Vertex Set (DFVS) problem. The DFVS problem is to find a minimum subset X ⊆ V in a given directed graph G = (V,E) such that, when all vertices of X and their adjacent edges are deleted from G, the remainder is acyclic. Overall, the challenge had 90 participants from 26 teams, 12 countries, and 3 continents that submitted their implementations to this year’s competition. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.

Cite as

Ernestine Großmann, Tobias Heuer, Christian Schulz, and Darren Strash. The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.IPEC.2022.26,
  author =	{Gro{\ss}mann, Ernestine and Heuer, Tobias and Schulz, Christian and Strash, Darren},
  title =	{{The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.26},
  URN =		{urn:nbn:de:0030-drops-173826},
  doi =		{10.4230/LIPIcs.IPEC.2022.26},
  annote =	{Keywords: Feedback Vertex Set, Algorithm Engineering, FPT, Kernelization, Heuristics}
}
Document
Complete Volume
LIPIcs, Volume 233, SEA 2022, Complete Volume

Authors: Christian Schulz and Bora Uçar

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
LIPIcs, Volume 233, SEA 2022, Complete Volume

Cite as

20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 1-434, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Proceedings{schulz_et_al:LIPIcs.SEA.2022,
  title =	{{LIPIcs, Volume 233, SEA 2022, Complete Volume}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{1--434},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022},
  URN =		{urn:nbn:de:0030-drops-165331},
  doi =		{10.4230/LIPIcs.SEA.2022},
  annote =	{Keywords: LIPIcs, Volume 233, SEA 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Christian Schulz and Bora Uçar

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{schulz_et_al:LIPIcs.SEA.2022.0,
  author =	{Schulz, Christian and U\c{c}ar, Bora},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.0},
  URN =		{urn:nbn:de:0030-drops-165342},
  doi =		{10.4230/LIPIcs.SEA.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Discrete Hyperbolic Random Graph Model

Authors: Dorota Celińska-Kopczyńska and Eryk Kopczyński

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
The hyperbolic random graph model (HRG) has proven useful in the analysis of scale-free networks, which are ubiquitous in many fields, from social network analysis to biology. However, working with this model is algorithmically and conceptually challenging because of the nature of the distances in the hyperbolic plane. In this paper, we propose a discrete variant of the HRG model (DHRG) where nodes are mapped to the vertices of a triangulation; our algorithms allow us to work with this model in a simple yet efficient way. We present experimental results conducted on networks, both real-world and simulated, to evaluate the practical benefits of DHRG in comparison to the HRG model.

Cite as

Dorota Celińska-Kopczyńska and Eryk Kopczyński. Discrete Hyperbolic Random Graph Model. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{celinskakopczynska_et_al:LIPIcs.SEA.2022.1,
  author =	{Celi\'{n}ska-Kopczy\'{n}ska, Dorota and Kopczy\'{n}ski, Eryk},
  title =	{{Discrete Hyperbolic Random Graph Model}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.1},
  URN =		{urn:nbn:de:0030-drops-165356},
  doi =		{10.4230/LIPIcs.SEA.2022.1},
  annote =	{Keywords: hyperbolic geometry, scale-free networks, routing, tessellation}
}
Document
Solving and Generating Nagareru Puzzles

Authors: Masakazu Ishihata and Fumiya Tokumasu

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
Solving paper-and-pencil puzzles is fun for people, and their analysis is also an essential issue in computational complexity theory. There are some practically efficient solvers for some NP-complete puzzles; however, the automatic generation of interesting puzzle instances still stands out as a complex problem because it requires checking whether the generated instance has a unique solution. In this paper, we focus on a puzzle called Nagareru and propose two methods: one is for implicitly enumerating all the solutions of its instance, and the other is for efficiently generating an instance with a unique solution. The former constructs a ZDD that implicitly represents all the solutions. The latter employs the ZDD-based solver as a building block to check the uniqueness of the solution of generated instances. We experimentally showed that the ZDD-based solver was drastically faster than a CSP-based solver, and our generation method created an interesting instance in a reasonable time.

Cite as

Masakazu Ishihata and Fumiya Tokumasu. Solving and Generating Nagareru Puzzles. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ishihata_et_al:LIPIcs.SEA.2022.2,
  author =	{Ishihata, Masakazu and Tokumasu, Fumiya},
  title =	{{Solving and Generating Nagareru Puzzles}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.2},
  URN =		{urn:nbn:de:0030-drops-165366},
  doi =		{10.4230/LIPIcs.SEA.2022.2},
  annote =	{Keywords: Paper-and-pencil puzzle, SAT, CSP, ZDD}
}
Document
Fast Computation of Shortest Smooth Paths and Uniformly Bounded Stretch with Lazy RPHAST

Authors: Tim Zeitz

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
We study the shortest smooth path problem (SSPP), which is motivated by traffic-aware routing in road networks. The goal is to compute the fastest route according to the current traffic situation while avoiding undesired detours, such as briefly using a parking area to bypass a jammed highway. Detours are prevented by limiting the uniformly bounded stretch (UBS) with respect to a second weight function which disregards the traffic situation. The UBS is a path quality metric which measures the maximum relative length of detours on a path. In this paper, we settle the complexity of the SSPP and show that it is strongly NP-complete. We then present practical algorithms to solve the problem on continental-sized road networks both heuristically and exactly. A crucial building block of these algorithms is the UBS evaluation. We propose a novel algorithm to compute the UBS with only a few shortest path computations on typical paths. All our algorithms utilize Lazy RPHAST, a recently proposed technique to incrementally compute distances from many vertices towards a common target. An extensive evaluation shows that our algorithms outperform competing SSPP algorithms by up to two orders of magnitude and that our new UBS algorithm is the first to consistently compute exact UBS values in a matter of milliseconds.

Cite as

Tim Zeitz. Fast Computation of Shortest Smooth Paths and Uniformly Bounded Stretch with Lazy RPHAST. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{zeitz:LIPIcs.SEA.2022.3,
  author =	{Zeitz, Tim},
  title =	{{Fast Computation of Shortest Smooth Paths and Uniformly Bounded Stretch with Lazy RPHAST}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.3},
  URN =		{urn:nbn:de:0030-drops-165378},
  doi =		{10.4230/LIPIcs.SEA.2022.3},
  annote =	{Keywords: realistic road networks, route planning, shortest paths, traffic-aware routing, live traffic, uniformly bounded stretch}
}
Document
Fast Succinct Retrieval and Approximate Membership Using Ribbon

Authors: Peter C. Dillinger, Lorenz Hübschle-Schneider, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
A retrieval data structure for a static function f: S → {0,1}^r supports queries that return f(x) for any x ∈ S. Retrieval data structures can be used to implement a static approximate membership query data structure (AMQ), i.e., a Bloom filter alternative, with false positive rate 2^{-r}. The information-theoretic lower bound for both tasks is r|S| bits. While succinct theoretical constructions using (1+o(1))r|S| bits were known, these could not achieve very small overheads in practice because they have an unfavorable space-time tradeoff hidden in the asymptotic costs or because small overheads would only be reached for physically impossible input sizes. With bumped ribbon retrieval (BuRR), we present the first practical succinct retrieval data structure. In an extensive experimental evaluation BuRR achieves space overheads well below 1% while being faster than most previously used retrieval data structures (typically with space overheads at least an order of magnitude larger) and faster than classical Bloom filters (with space overhead ≥ 44%). This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We additionally describe homogeneous ribbon filter AMQs, which are even simpler and faster at the price of slightly larger space overhead.

Cite as

Peter C. Dillinger, Lorenz Hübschle-Schneider, Peter Sanders, and Stefan Walzer. Fast Succinct Retrieval and Approximate Membership Using Ribbon. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dillinger_et_al:LIPIcs.SEA.2022.4,
  author =	{Dillinger, Peter C. and H\"{u}bschle-Schneider, Lorenz and Sanders, Peter and Walzer, Stefan},
  title =	{{Fast Succinct Retrieval and Approximate Membership Using Ribbon}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.4},
  URN =		{urn:nbn:de:0030-drops-165385},
  doi =		{10.4230/LIPIcs.SEA.2022.4},
  annote =	{Keywords: AMQ, Bloom filter, dictionary, linear algebra, randomized algorithm, retrieval data structure, static function data structure, succinct data structure, perfect hashing}
}
Document
Parallel Flow-Based Hypergraph Partitioning

Authors: Lars Gottesbüren, Tobias Heuer, and Peter Sanders

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
We present a shared-memory parallelization of flow-based refinement, which is considered the most powerful iterative improvement technique for hypergraph partitioning at the moment. Flow-based refinement works on bipartitions, so current sequential partitioners schedule it on different block pairs to improve k-way partitions. We investigate two different sources of parallelism: a parallel scheduling scheme and a parallel maximum flow algorithm based on the well-known push-relabel algorithm. In addition to thoroughly engineered implementations, we propose several optimizations that substantially accelerate the algorithm in practice, enabling the use on extremely large hypergraphs (up to 1 billion pins). We integrate our approach in the state-of-the-art parallel multilevel framework Mt-KaHyPar and conduct extensive experiments on a benchmark set of more than 500 real-world hypergraphs, to show that the partition quality of our code is on par with the highest quality sequential code (KaHyPar), while being an order of magnitude faster with 10 threads.

Cite as

Lars Gottesbüren, Tobias Heuer, and Peter Sanders. Parallel Flow-Based Hypergraph Partitioning. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.SEA.2022.5,
  author =	{Gottesb\"{u}ren, Lars and Heuer, Tobias and Sanders, Peter},
  title =	{{Parallel Flow-Based Hypergraph Partitioning}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.5},
  URN =		{urn:nbn:de:0030-drops-165393},
  doi =		{10.4230/LIPIcs.SEA.2022.5},
  annote =	{Keywords: multilevel hypergraph partitioning, shared-memory algorithms, maximum flow}
}
Document
Routing in Multimodal Transportation Networks with Non-Scheduled Lines

Authors: Darko Drakulic, Christelle Loiodice, and Vassilissa Lehoux

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
Over the last decades, new mobility offers have emerged to enlarge the coverage and the accessibility of public transportation systems. In many areas, public transit now incorporates on-demand transport lines, that can be activated at user need. In this paper, we propose to integrate lines without predefined schedules but with predefined stop sequences into a state-of-the-art trip planning algorithm for public transit, the Trip-Based Public Transit Routing algorithm [Witt, 2015]. We extend this algorithm to non-scheduled lines and explain how to model other modes of transportation, such as bike sharing, with this approach. The resulting algorithm is exact and optimizes two criteria: the earliest arrival time and the minimal number of transfers. Experiments on two large datasets show the interest of the proposed method over a baseline modelling.

Cite as

Darko Drakulic, Christelle Loiodice, and Vassilissa Lehoux. Routing in Multimodal Transportation Networks with Non-Scheduled Lines. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{drakulic_et_al:LIPIcs.SEA.2022.6,
  author =	{Drakulic, Darko and Loiodice, Christelle and Lehoux, Vassilissa},
  title =	{{Routing in Multimodal Transportation Networks with Non-Scheduled Lines}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.6},
  URN =		{urn:nbn:de:0030-drops-165406},
  doi =		{10.4230/LIPIcs.SEA.2022.6},
  annote =	{Keywords: Multimodal routing, on-demand public transportation, bicriteria shortest paths}
}
  • Refine by Author
  • 19 Schulz, Christian
  • 5 Henzinger, Monika
  • 5 Heuer, Tobias
  • 4 Gottesbüren, Lars
  • 3 Hanauer, Kathrin
  • Show More...

  • Refine by Classification
  • 15 Mathematics of computing → Graph algorithms
  • 7 Theory of computation → Design and analysis of algorithms
  • 7 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Shortest paths
  • 2 Applied computing → Transportation
  • Show More...

  • Refine by Keyword
  • 4 Algorithm Engineering
  • 4 graph partitioning
  • 3 Graph Partitioning
  • 3 graph algorithms
  • 3 parallel algorithms
  • Show More...

  • Refine by Type
  • 47 document
  • 1 volume

  • Refine by Publication Year
  • 30 2022
  • 4 2020
  • 4 2023
  • 3 2021
  • 2 2006
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail