3 Search Results for "Blair, Howard"

Document
DOI: 10.4230/LIPIcs.SEA.2026.26
Engineering Algorithms for Dynamic Greedy Set Cover

Authors: Amitai Uzrad

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks - such as [GKKP(STOC'17); SU(STOC'23); SUZ(FOCS'24)] - which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time - the time required to update the solution following each insertion/deletion - and recourse - the number of changes made to the solution per update. Each algorithm uses a parameter β to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios.
Cite as

Amitai Uzrad. Engineering Algorithms for Dynamic Greedy Set Cover. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uzrad:LIPIcs.SEA.2026.26,
  author =	{Uzrad, Amitai},
  title =	{{Engineering Algorithms for Dynamic Greedy Set Cover}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.26},
  URN =		{urn:nbn:de:0030-drops-260308},
  doi =		{10.4230/LIPIcs.SEA.2026.26},
  annote =	{Keywords: Dynamic graphs, set cover, recourse}
}
Document
Survey
DOI: 10.4230/TGDK.3.1.3
Uncertainty Management in the Construction of Knowledge Graphs: A Survey

Authors: Lucas Jarnac, Yoan Chabot, and Miguel Couceiro

Published in: TGDK, Volume 3, Issue 1 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 1

Abstract
Knowledge Graphs (KGs) are a major asset for companies thanks to their great flexibility in data representation and their numerous applications, e.g., vocabulary sharing, Q&A or recommendation systems. To build a KG, it is a common practice to rely on automatic methods for extracting knowledge from various heterogeneous sources. However, in a noisy and uncertain world, knowledge may not be reliable and conflicts between data sources may occur. Integrating unreliable data would directly impact the use of the KG, therefore such conflicts must be resolved. This could be done manually by selecting the best data to integrate. This first approach is highly accurate, but costly and time-consuming. That is why recent efforts focus on automatic approaches, which represent a challenging task since it requires handling the uncertainty of extracted knowledge throughout its integration into the KG. We survey state-of-the-art approaches in this direction and present constructions of both open and enterprise KGs. We then describe different knowledge extraction methods and discuss downstream tasks after knowledge acquisition, including KG completion using embedding models, knowledge alignment, and knowledge fusion in order to address the problem of knowledge uncertainty in KG construction. We conclude with a discussion on the remaining challenges and perspectives when constructing a KG taking into account uncertainty.
Cite as

Lucas Jarnac, Yoan Chabot, and Miguel Couceiro. Uncertainty Management in the Construction of Knowledge Graphs: A Survey. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 1, pp. 3:1-3:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{jarnac_et_al:TGDK.3.1.3,
  author =	{Jarnac, Lucas and Chabot, Yoan and Couceiro, Miguel},
  title =	{{Uncertainty Management in the Construction of Knowledge Graphs: A Survey}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:48},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.1.3},
  URN =		{urn:nbn:de:0030-drops-233733},
  doi =		{10.4230/TGDK.3.1.3},
  annote =	{Keywords: Knowledge reconciliation, Uncertainty, Heterogeneous sources, Knowledge graph construction}
}
Document
DOI: 10.4230/DagSemProc.06341.4
Elementary Differential Calculus on Discrete, Continuous and Hybrid Spaces

Authors: Howard Blair

Published in: Dagstuhl Seminar Proceedings, Volume 6341, Computational Structures for Modelling Space, Time and Causality (2007)

Abstract
We unify a variety of continuous and discrete types of change of state phenomena using a scheme whose instances are differential calculi on structures that embrace both topological spaces and graphs as well as hybrid ramifications of such structures. These calculi include the elementary differential calculus on real and complex vector spaces. One class of spaces that has been increasingly receiving attention in recent years is the class of convergence spaces [cf. Heckmann, R., TCS v.305, (159--186)(2003)]. The class of convergence spaces together with the continuous functions among convergence spaces forms a Cartesian-closed category CONV that contains as full subcategories both the category TOP of topological spaces and an embedding of the category DIGRAPH of reflexive directed graphs. (More can importantly be said about these embeddings.) These properties of CONV serve to assure that we can construct continuous products of continuous functions, and that there is always at least one convergence structure available in function spaces with respect to which the operations of function application and composition are continuous. The containment of TOP and DIGRAPH in CONV allows to combine arbitrary topological spaces with discrete structures (as represented by digraphs) to obtain hybrid structures, which generally are not topological spaces. We give a differential calculus scheme in CONV that addresses three issues in particular. 1. For convergence spaces $X$ and $Y$ and function $f: X longrightarrow Y$, the scheme gives necessary and sufficient conditions for a candidate differential $df: X longrightarrow Y$ to be a (not necessarily "the", depending on the spaces involved) differential of $f$ at $x_0$. 2. The chain rule holds and the differential relation between functions distributes over Cartesian products: e.g. if $Df$, $Dg$ and $Dh$ are, respectively, differentials of $f$ at $(g(x_0),h(x_0))$ and $g$ and $h$ at $x_0$, then $Df circ (Dg times Dh)$ is a differential of $f circ (g times h)$ at $x_0$. 3. When specialized to real and complex vector spaces, the scheme is in agreement with ordinary elementary differential calculus on these spaces. Moreover, with two additional constraints having to do with self-differentiation of differentials and translation invariance (for example, a linear operator on, say, $C^2$, is its own differential everywhere) there is a (unique) maximum differential calculus in CONV.
Cite as

Howard Blair. Elementary Differential Calculus on Discrete, Continuous and Hybrid Spaces. In Computational Structures for Modelling Space, Time and Causality. Dagstuhl Seminar Proceedings, Volume 6341, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{blair:DagSemProc.06341.4,
  author =	{Blair, Howard},
  title =	{{Elementary Differential Calculus on Discrete, Continuous and Hybrid Spaces}},
  booktitle =	{Computational Structures for Modelling Space, Time and Causality},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6341},
  editor =	{Ralph Kopperman and Prakash Panangaden and Michael B. Smyth and Dieter Spreen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06341.4},
  URN =		{urn:nbn:de:0030-drops-8956},
  doi =		{10.4230/DagSemProc.06341.4},
  annote =	{Keywords: Hybrid space, convergence space, differential, calculus, chain rule, hybrid dynamical system, discrete structure, topological space}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2007

  • Refine by Author
  • 1 Blair, Howard
  • 1 Chabot, Yoan
  • 1 Couceiro, Miguel
  • 1 Jarnac, Lucas
  • 1 Uzrad, Amitai

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 TGDK
  • 1 DagSemProc

  • Refine by Classification
  • 1 Information systems → Graph-based database models
  • 1 Information systems → Information integration
  • 1 Information systems → Uncertainty
  • 1 Theory of computation → Dynamic graph algorithms

  • Refine by Keyword
  • 1 Dynamic graphs
  • 1 Heterogeneous sources
  • 1 Hybrid space
  • 1 Knowledge graph construction
  • 1 Knowledge reconciliation
  • 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