5 Search Results for "Johnson, Timothy"

Document
DOI: 10.4230/LIPIcs.SEA.2023.15
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.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
DOI: 10.4230/LIPIcs.FUN.2021.4
Taming the Knight’s Tour: Minimizing Turns and Crossings

Authors: Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We introduce two new metrics of "simplicity" for knight’s tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.5n+O(1) turns and 13n+O(1) crossings on a n× n board, and we show lower bounds of (6-ε)n and 4n-O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 19/12+o(1) and 13/4+o(1). We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1,4)-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.
Cite as

Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda. Taming the Knight’s Tour: Minimizing Turns and Crossings. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 4:1-4:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.FUN.2021.4,
  author =	{Besa, Juan Jose and Johnson, Timothy and Mamano, Nil and Osegueda, Martha C.},
  title =	{{Taming the Knight’s Tour: Minimizing Turns and Crossings}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.4},
  URN =		{urn:nbn:de:0030-drops-127654},
  doi =		{10.4230/LIPIcs.FUN.2021.4},
  annote =	{Keywords: Graph Drawing, Chess, Hamiltonian Cycle, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.81
Optimally Sorting Evolving Data

Authors: Juan Jose Besa, William E. Devanny, David Eppstein, Michael T. Goodrich, and Timothy Johnson

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.
Cite as

Juan Jose Besa, William E. Devanny, David Eppstein, Michael T. Goodrich, and Timothy Johnson. Optimally Sorting Evolving Data. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 81:1-81:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.ICALP.2018.81,
  author =	{Besa, Juan Jose and Devanny, William E. and Eppstein, David and Goodrich, Michael T. and Johnson, Timothy},
  title =	{{Optimally Sorting Evolving Data}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.81},
  URN =		{urn:nbn:de:0030-drops-90858},
  doi =		{10.4230/LIPIcs.ICALP.2018.81},
  annote =	{Keywords: Sorting, Evolving data, Insertion sort}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.24
Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs

Authors: Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
A square-contact representation of a planar graph G = (V,E) maps vertices in V to interior-disjoint axis-aligned squares in the plane and edges in E to adjacencies between the sides of the corresponding squares. In this paper, we study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points. We characterize the partial 2-trees and the triconnected cycle-trees allowing for such representations. For partial 2-trees our characterization uses a simple forbidden subgraph whose structure forces a separating triangle in any embedding. For the triconnected cycle-trees, a subclass of the triconnected simply-nested graphs, we use a new structural decomposition for the graphs in this family, which may be of independent interest. Finally, we study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index.
Cite as

Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson. Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 24:1-24:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2017.24,
  author =	{Da Lozzo, Giordano and Devanny, William E. and Eppstein, David and Johnson, Timothy},
  title =	{{Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.24},
  URN =		{urn:nbn:de:0030-drops-82675},
  doi =		{10.4230/LIPIcs.ISAAC.2017.24},
  annote =	{Keywords: Square-Contact Representations, Partial 2-Trees, Simply-Nested Graphs}
}
Document
DOI: 10.4230/LITES-v001-i002-a001
Blocking Optimality in Distributed Real-Time Locking Protocols

Authors: Björn Bernhard Brandenburg

Published in: LITES, Volume 1, Issue 2 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 2

Abstract
Lower and upper bounds on the maximum priority inversion blocking (pi-blocking) that is generally unavoidable in distributed multiprocessor real-time locking protocols (where resources may be accessed only from specific synchronization processors) are established. Prior work on suspension-based shared-memory multiprocessor locking protocols (which require resources to be accessible from all processors) has established asymptotically tight bounds of Ω(m) and Ω(n) maximum pi-blocking under suspension-oblivious and suspension-aware analysis, respectively, where m denotes the total number of processors and n denotes the number of tasks. In this paper, it is shown that, in the case of distributed semaphore protocols, there exist two different task allocation scenarios that give rise to distinct lower bounds. In the case of co-hosted task allocation, where application tasks may also be assigned to synchronization processors (i.e., processors hosting critical sections), Ω(Φ · n) maximum pi-blocking is unavoidable for some tasks under any locking protocol under both suspension-aware and suspension-oblivious schedulability analysis, where Φ denotes the ratio of the maximum response time to the shortest period. In contrast, in the case of disjoint task allocation (i.e., if application tasks may not be assigned to synchronization processors), only Ω(m) and Ω(n) maximum pi-blocking is fundamentally unavoidable under suspension-oblivious and suspension-aware analysis, respectively, as in the shared-memory case. These bounds are shown to be asymptotically tight with the construction of two new distributed real-time locking protocols that ensure O(m) and O(n) maximum pi-blocking under suspension-oblivious and suspension-aware analysis, respectively.
Cite as

Björn Bernhard Brandenburg. Blocking Optimality in Distributed Real-Time Locking Protocols. In LITES, Volume 1, Issue 2 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 2, pp. 01:1-01:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{brandenburg:LITES-v001-i002-a001,
  author =	{Brandenburg, Bj\"{o}rn Bernhard},
  title =	{{Blocking Optimality in Distributed Real-Time Locking Protocols}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:22},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v001-i002-a001},
  doi =		{10.4230/LITES-v001-i002-a001},
  annote =	{Keywords: Distributed multiprocessor real-time systems, Real-time locking, Priority inversion, Blocking optimality}
}
  • Refine by Author
  • 3 Johnson, Timothy
  • 2 Besa, Juan Jose
  • 2 Devanny, William E.
  • 2 Eppstein, David
  • 1 Brandenburg, Björn Bernhard
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time systems
  • 1 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Software and its engineering → Synchronization
  • 1 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Blocking optimality
  • 1 Chess
  • 1 Distributed multiprocessor real-time systems
  • 1 Evolving data
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2014
  • 1 2017
  • 1 2018
  • 1 2020
  • 1 2023

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact