2 Search Results for "Martínez-Muñoz, Tomás"

Document

Survey

Semantic Web: Past, Present, and Future

Authors: Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1

Abstract

Ever since the vision was formulated, the Semantic Web has inspired many generations of innovations. Semantic technologies have been used to share vast amounts of information on the Web, enhance them with semantics to give them meaning, and enable inference and reasoning on them. Throughout the years, semantic technologies, and in particular knowledge graphs, have been used in search engines, data integration, enterprise settings, and machine learning. In this paper, we recap the classical concepts and foundations of the Semantic Web as well as modern and recent concepts and applications, building upon these foundations. The classical topics we cover include knowledge representation, creating and validating knowledge on the Web, reasoning and linking, and distributed querying. We enhance this classical view of the so-called "Semantic Web Layer Cake" with an update of recent concepts that include provenance, security and trust, as well as a discussion of practical impacts from industry-led contributions. We conclude with an outlook on the future directions of the Semantic Web. This is a living document. If you like to contribute, please contact the first author and visit: https://github.com/ascherp/semantic-web-primer

Cite as

Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal. Semantic Web: Past, Present, and Future. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 3:1-3:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{scherp_et_al:TGDK.2.1.3,
  author =	{Scherp, Ansgar and Groener, Gerd and \v{S}koda, Petr and Hose, Katja and Vidal, Maria-Esther},
  title =	{{Semantic Web: Past, Present, and Future}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:37},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.3},
  URN =		{urn:nbn:de:0030-drops-198607},
  doi =		{10.4230/TGDK.2.1.3},
  annote =	{Keywords: Linked Open Data, Semantic Web Graphs, Knowledge Graphs}
}

Document

DOI: 10.4230/LIPIcs.ESA.2021.67

FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees

Authors: Tomás Martínez-Muñoz and Andreas Wiese

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract

We study the unsplittable flow on trees (UFT) problem in which we are given a tree with capacities on its edges and a set of tasks, where each task is described by a path and a demand. Our goal is to select a subset of the given tasks of maximum size such that the demands of the selected tasks respect the edge capacities. The problem models throughput maximization in tree networks. The best known approximation ratio for (unweighted) UFT is O(log n). We study the problem under the angle of FPT and FPT-approximation algorithms. We prove that - UFT is FPT if the parameters are the cardinality k of the desired solution and the number of different task demands in the input, - UFT is FPT under (1+δ)-resource augmentation of the edge capacities for parameters k and 1/δ, and - UFT admits an FPT-5-approximation algorithm for parameter k. One key to our results is to compute structured hitting sets of the input edges which partition the given tree into O(k) clean components. This allows us to guess important properties of the optimal solution. Also, in some settings we can compute core sets of subsets of tasks out of which at least one task i is contained in the optimal solution. These sets have bounded size, and hence we can guess this task i easily. A consequence of our results is that the integral multicommodity flow problem on trees is FPT if the parameter is the desired amount of sent flow. Also, even under (1+δ)-resource augmentation UFT is APX-hard, and hence our FPT-approximation algorithm for this setting breaks this boundary.

Cite as

Tomás Martínez-Muñoz and Andreas Wiese. FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{martinezmunoz_et_al:LIPIcs.ESA.2021.67,
  author =	{Mart{\'\i}nez-Mu\~{n}oz, Tom\'{a}s and Wiese, Andreas},
  title =	{{FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{67:1--67:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.67},
  URN =		{urn:nbn:de:0030-drops-146486},
  doi =		{10.4230/LIPIcs.ESA.2021.67},
  annote =	{Keywords: FPT algorithms, FPT-approximation algorithms, packing problems, unsplittable flow, trees}
}

Refine by Author
1 Groener, Gerd
1 Hose, Katja
1 Martínez-Muñoz, Tomás
1 Scherp, Ansgar
1 Vidal, Maria-Esther
Show More...

Refine by Classification
1 Computing methodologies → Knowledge representation and reasoning
1 Computing methodologies → Ontology engineering
1 Information systems → Markup languages
1 Information systems → Semantic web description languages
1 Theory of computation → Packing and covering problems

Refine by Keyword
1 FPT algorithms
1 FPT-approximation algorithms
1 Knowledge Graphs
1 Linked Open Data
1 Semantic Web Graphs
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2021
1 2024