2 Search Results for "Gerke, Jan"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.10
Robotic Arm Rotation: Standing up Is Harder Than You Think

Authors: Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study motion-planning problems for planar robotic arms that rotate around fixed centers while avoiding collisions. In the SM-RAMP model, each unit-length arm may rotate at most once; the question is whether all arms can be rotated to the vertical position. We resolve an open problem of Bousquet et al. [Bousquet et al., 2026] by proving that SM-RAMP is NP-complete, even in the horizontal-to-vertical setting. Our hardness proof uses a structural analysis of rotation-propagation chains and introduces a combinatorial abstraction of independent interest, the Lighthouse Propagation problem, which we show is itself NP-complete. We then consider the multi-move variant MM-RAMP, where each arm may rotate multiple times among a fixed set of allowed angles (or orientations). We prove that MM-RAMP is PSPACE-complete even when each arm has only a few allowed angles, in sharp contrast with the single-move case. Finally, we give two fixed-parameter tractable algorithms: for MAX-SM-RAMP parameterized by the number k of arms to be made vertical, and for 2A-MM-RAMP (restricted to horizontal and vertical) parameterized by the number 𝓁 of allowed rotations.
Cite as

Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig. Robotic Arm Rotation: Standing up Is Harder Than You Think. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.SWAT.2026.10,
  author =	{Bousquet, Nicolas and Connor, Frank and El Sabeh, Remy and Langevin, Louis-Roy and Mouawad, Amer E. and Nishimura, Naomi and Totschnig, Agnes},
  title =	{{Robotic Arm Rotation: Standing up Is Harder Than You Think}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.10},
  URN =		{urn:nbn:de:0030-drops-260467},
  doi =		{10.4230/LIPIcs.SWAT.2026.10},
  annote =	{Keywords: search, optimization, robotics, robotic arms, parameterized complexity, computational geometry, combinatorial reconfiguration}
}
Document
DOI: 10.4230/DagSemProc.04411.7
Charging Service Compositions in a Service-Oriented Peer-to-Peer Network

Authors: Jan Gerke

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
Today, peer-to-peer (P2P) networks, e.g., filesharing networks like Gnutella, are specialised towards specific purposes. This shortcoming is addressed by introducing a new middleware for P2P networks. The middleware supports the deployment and use of services inside a P2P network. The middleware can be adapted through plug-ins. It includes service negotiation mechanisms which support the creation of legally enforceable service level agreements (SLAs) by using strong identities. This allows to reliably compose services into new value-added services. The business model of service composers has been investigated. The question of how to charge for such service compositions is addressed by introducing an event-based charging model. The events are to be applied in a service consumer's utility function as well as service composers' and service providers' tariff functions. Finally, the relation of these functions determines the profits of a service composer.
Cite as

Jan Gerke. Charging Service Compositions in a Service-Oriented Peer-to-Peer Network. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gerke:DagSemProc.04411.7,
  author =	{Gerke, Jan},
  title =	{{Charging Service Compositions in a Service-Oriented Peer-to-Peer Network}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.7},
  URN =		{urn:nbn:de:0030-drops-906},
  doi =		{10.4230/DagSemProc.04411.7},
  annote =	{Keywords: peer-to-peer middleware service negotiation , service level agreements , service composition , service charging}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2005

  • Refine by Author
  • 1 Bousquet, Nicolas
  • 1 Connor, Frank
  • 1 El Sabeh, Remy
  • 1 Gerke, Jan
  • 1 Langevin, Louis-Roy
  • Show More...

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

  • Refine by Classification
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 combinatorial reconfiguration
  • 1 computational geometry
  • 1 optimization
  • 1 parameterized complexity
  • 1 peer-to-peer middleware service negotiation
  • 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