4 Search Results for "Vincze, Markus"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/DagRep.4.2.79
Robots Learning from Experiences (Dagstuhl Seminar 14081)

Authors: Anthony G. Cohn, Bernd Neumann, Alessandro Saffiotti, and Markus Vincze

Published in: Dagstuhl Reports, Volume 4, Issue 2 (2014)

Abstract
This report documents the programme and the outcomes of Dagstuhl Seminar 14081 "Robots Learning from Experiences". The report begins with a summary comprising information about the seminar topics, the programme, important discussion points, and conclusions. The main body of the report consists of the abstracts of 25 presentations given at the seminar, and of four reports about discussion groups.
Cite as

Anthony G. Cohn, Bernd Neumann, Alessandro Saffiotti, and Markus Vincze. Robots Learning from Experiences (Dagstuhl Seminar 14081). In Dagstuhl Reports, Volume 4, Issue 2, pp. 79-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{cohn_et_al:DagRep.4.2.79,
  author =	{Cohn, Anthony G. and Neumann, Bernd and Saffiotti, Alessandro and Vincze, Markus},
  title =	{{Robots Learning from Experiences (Dagstuhl Seminar 14081)}},
  pages =	{79--109},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{2},
  editor =	{Cohn, Anthony G. and Neumann, Bernd and Saffiotti, Alessandro and Vincze, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.2.79},
  URN =		{urn:nbn:de:0030-drops-45465},
  doi =		{10.4230/DagRep.4.2.79},
  annote =	{Keywords: Learning, experiences, cognitive systems}
}
Document
DOI: 10.4230/DagSemProc.09431.1
09421 Abstracts Collection – From Form to Function

Authors: Darius Burschka, Heiner Deubel, Danica Kragic, and Markus Vincze

Published in: Dagstuhl Seminar Proceedings, Volume 9431, From Form to Function (2010)

Abstract
From October 18 to October 23, 2009 the Dagstuhl Seminar 09431 ``From Form to Function '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Darius Burschka, Heiner Deubel, Danica Kragic, and Markus Vincze. 09421 Abstracts Collection – From Form to Function. In From Form to Function. Dagstuhl Seminar Proceedings, Volume 9431, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{burschka_et_al:DagSemProc.09431.1,
  author =	{Burschka, Darius and Deubel, Heiner and Kragic, Danica and Vincze, Markus},
  title =	{{09421 Abstracts Collection – From Form to Function}},
  booktitle =	{From Form to Function},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9431},
  editor =	{Darius Burschka and Heiner Deubel and Danica Kragic and Markus Vincze},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09431.1},
  URN =		{urn:nbn:de:0030-drops-24197},
  doi =		{10.4230/DagSemProc.09431.1},
  annote =	{Keywords: Recognition of structure, form and shape, affordances, perception action loop, Grasping}
}
Document
DOI: 10.4230/DagSemProc.08091.2
Abstraction, ontology and task-guidance for visual perception in robots

Authors: Matthias Schlemmer and Markus Vincze

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)

Abstract
For solving recognition tasks in order to navigate in unknown environments and to manipulate objects, humans seem to use at least the following crucial capabilities: abstraction (for storing higher-level concepts of things), common sense knowledge and prediction. Whereas the first and second provide the basis for situated recognition, the second and third serve for pruning the search space as it helps anticipating what (in an abstract sense) they will see next and where. The main goal of our current research is, how we could use such a kind of "common sense world knowledge" for guiding visual perception and understanding scenes. Therefore, we are combining an owl-ontology with the output of vision tools. The additional use of abstraction techniques tries to establish the possibility of detecting higher level concepts, such as arches composed of a variable number of parts. The goal is to finally find concepts such as doors and tables in arbitrary scenes in order to arrive at a generic recognition tool for home robots. The ontology should additionally provide task-specific information about the things to detect.
Cite as

Matthias Schlemmer and Markus Vincze. Abstraction, ontology and task-guidance for visual perception in robots. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{schlemmer_et_al:DagSemProc.08091.2,
  author =	{Schlemmer, Matthias and Vincze, Markus},
  title =	{{Abstraction, ontology and task-guidance for visual perception in robots}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.2},
  URN =		{urn:nbn:de:0030-drops-16081},
  doi =		{10.4230/DagSemProc.08091.2},
  annote =	{Keywords: Abstraction, ontology, task, vision}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2014
  • 1 2010
  • 1 2008

  • Refine by Author
  • 3 Vincze, Markus
  • 1 Blažej, Václav
  • 1 Burschka, Darius
  • 1 Cohn, Anthony G.
  • 1 Deubel, Heiner
  • Show More...

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

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Abstraction
  • 1 Directed TSP
  • 1 Grasping
  • 1 Learning
  • 1 Recognition of structure
  • 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