3 Search Results for "Mohror, Kathryn"

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
DOI: 10.4230/DagRep.11.7.16
Understanding I/O Behavior in Scientific and Data-Intensive Computing (Dagstuhl Seminar 21332)

Authors: Philip Carns, Julian Kunkel, Kathryn Mohror, and Martin Schulz

Published in: Dagstuhl Reports, Volume 11, Issue 7 (2021)

Abstract
Two key changes are driving an immediate need for deeper understanding of I/O workloads in high-performance computing (HPC): applications are evolving beyond the traditional bulk-synchronous models to include integrated multistep workflows, in situ analysis, artificial intelligence, and data analytics methods; and storage systems designs are evolving beyond a two-tiered file system and archive model to complex hierarchies containing temporary, fast tiers of storage close to compute resources with markedly different performance properties. Both of these changes represent a significant departure from the decades-long status quo and require investigation from storage researchers and practitioners to understand their impacts on overall I/O performance. Without an in-depth understanding of I/O workload behavior, storage system designers, I/O middleware developers, facility operators, and application developers will not know how best to design or utilize the additional tiers for optimal performance of a given I/O workload. The goal of this Dagstuhl Seminar was to bring together experts in I/O performance analysis and storage system architecture to collectively evaluate how our community is capturing and analyzing I/O workloads on HPC systems, identify any gaps in our methodologies, and determine how to develop a better in-depth understanding of their impact on HPC systems. Our discussions were lively and resulted in identifying critical needs for research in the area of understanding I/O behavior. We document those discussions in this report.
Cite as

Philip Carns, Julian Kunkel, Kathryn Mohror, and Martin Schulz. Understanding I/O Behavior in Scientific and Data-Intensive Computing (Dagstuhl Seminar 21332). In Dagstuhl Reports, Volume 11, Issue 7, pp. 16-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{carns_et_al:DagRep.11.7.16,
  author =	{Carns, Philip and Kunkel, Julian and Mohror, Kathryn and Schulz, Martin},
  title =	{{Understanding I/O Behavior in Scientific and Data-Intensive Computing (Dagstuhl Seminar 21332)}},
  pages =	{16--75},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{7},
  editor =	{Carns, Philip and Kunkel, Julian and Mohror, Kathryn and Schulz, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.7.16},
  URN =		{urn:nbn:de:0030-drops-155891},
  doi =		{10.4230/DagRep.11.7.16},
  annote =	{Keywords: I/O performance measurement, Understanding user I/O patterns, HPC I/O, I/O characterization}
}
Document
DOI: 10.4230/DagRep.7.5.97
Challenges and Opportunities of User-Level File Systems for HPC (Dagstuhl Seminar 17202)

Authors: André Brinkmann, Kathryn Mohror, and Weikuan Yu

Published in: Dagstuhl Reports, Volume 7, Issue 5 (2018)

Abstract
The performance gap between magnetic disks and data processing on HPC systems has become that huge that an efficient data processing can only be achieved by introducing non-volatile memory (NVRAM) as a new storage tier. Although the benefits of hierarchical storage have been adequately demonstrated to the point that the newest leadership class HPC systems will employ burst buffers, critical questions remain for supporting hierarchical storage systems, including: How should we present hierarchical storage systems to user applications, such that they are easy to use and that application code is portable across systems? How should we manage data movement through a storage hierarchy for best performance and resilience of data? How do the particular I/O use cases mandate the way we manage data? There have been many efforts to explore this space in the form of file systems, with increasingly more implemented at the user level. This is because it is relatively easy to swap in new, specialized user-level file systems for use by applications on a case-by-case basis, as opposed to the current mainstream approach of using general-purpose, system-level file systems which may not be optimized for HPC workloads and must be installed by administrators. In contrast, file systems at the user level can be tailored for specific HPC workloads for high performance and can be used by applications without administrator intervention. Many user-level file system developers have found themselves “having to reinvent the wheel” to implement various optimizations in their file systems. Thus, a main goal of this meeting was to bring together experts in I/O performance, file systems, and storage, and collectively explore the space of current and future problems and solutions for I/O on hierarchical storage systems in order to begin a community effort in enabling user-level file system support for HPC systems. We had a lively week of learning about each other’s approaches as well as unique I/O use cases that can influence the design of a community-driven file and storage system standards. The agenda for this meeting contained talks from participants on the following high level topics: HPC storage and I/O support today; what do HPC users need for I/O; existing user-level file system efforts; object stores and other alternative storage systems; and components for building user-level file systems. The talks were short and intended to be conversation starters for more in-depth discussions with the whole group. The participants engaged in lengthy discussions on various questions that arose from the talks including: Are we ready to program to a memory hierarchy versus block devices? Are the needs of HPC users reflected in our existing file systems and storage systems? Should we drop or keep POSIX moving forward? What do we mean when we say "user-level file system"? Do we all mean the same thing? How should the IO 500 benchmark be defined so it is fair and useful? and How are stage-in and stage-out actually going to work? The report for this seminar contains a record of the talks from the participants as well as the resulting discussions. Our hope is that the effort initiated during this seminar will result in long-term collaborations that will benefit the HPC community as a whole.
Cite as

André Brinkmann, Kathryn Mohror, and Weikuan Yu. Challenges and Opportunities of User-Level File Systems for HPC (Dagstuhl Seminar 17202). In Dagstuhl Reports, Volume 7, Issue 5, pp. 97-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{brinkmann_et_al:DagRep.7.5.97,
  author =	{Brinkmann, Andr\'{e} and Mohror, Kathryn and Yu, Weikuan},
  title =	{{Challenges and Opportunities of User-Level File Systems for HPC (Dagstuhl Seminar 17202)}},
  pages =	{97--139},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{5},
  editor =	{Brinkmann, Andr\'{e} and Mohror, Kathryn and Yu, Weikuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.5.97},
  URN =		{urn:nbn:de:0030-drops-82820},
  doi =		{10.4230/DagRep.7.5.97},
  annote =	{Keywords: High Performance Computing, I/O and Storage, Object Stores, User-level Storage Systems}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021
  • 1 2017

  • Refine by Author
  • 2 Mohror, Kathryn
  • 1 Brinkmann, André
  • 1 Carns, Philip
  • 1 El-Hayek, Antoine
  • 1 Hanauer, Kathrin
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 2 DagRep

  • Refine by Classification
  • 1 Networks → Network performance analysis
  • 1 Software and its engineering → Software design engineering
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 HPC I/O
  • 1 High Performance Computing
  • 1 I/O and Storage
  • 1 I/O characterization
  • 1 I/O performance measurement
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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