3 Search Results for "Damaschke, Peter"


Document
Distance-Based Solution of Patrolling Problems with Individual Waiting Times

Authors: Peter Damaschke

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
In patrolling problems, robots (or other vehicles) must perpetually visit certain points without exceeding given individual waiting times. Some obvious applications are monitoring, maintenance, and periodic fetching of resources. We propose a new generic formulation of the problem. As its main advantage, it enables a reduction of the multi-robot case to the one-robot case in a certain graph/hypergraph pair, which also relates the problem to some classic path problems in graphs: NP-hardness is shown by a reduction from the Hamiltonian cycle problem, and on the positive side, the formulation allows solution heuristics using distances in the mentioned graph. We demonstrate this approach for the case of two robots patrolling on a line, a problem whose complexity status is open, apart from approximation results. Specifically, we solve all instances with up to 6 equidistant points, and we find some surprising effects, e.g., critical problem instances (which are feasible instances that become infeasible when any waiting time is diminished) may contain rather large individual waiting times.

Cite as

Peter Damaschke. Distance-Based Solution of Patrolling Problems with Individual Waiting Times. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{damaschke:OASIcs.ATMOS.2021.14,
  author =	{Damaschke, Peter},
  title =	{{Distance-Based Solution of Patrolling Problems with Individual Waiting Times}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{14:1--14:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.14},
  URN =		{urn:nbn:de:0030-drops-148838},
  doi =		{10.4230/OASIcs.ATMOS.2021.14},
  annote =	{Keywords: Patrolling, Periodic scheduling, Shortest path, Well-quasi ordering}
}
Document
Lower Bound for Non-Adaptive Estimation of the Number of Defective Items

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
We prove that to estimate within a constant factor the number of defective items in a non-adaptive randomized group testing algorithm we need at least Omega~(log n) tests. This solves the open problem posed by Damaschke and Sheikh Muhammad in [Peter Damaschke and Azam Sheikh Muhammad, 2010; Peter Damaschke and Azam Sheikh Muhammad, 2010].

Cite as

Nader H. Bshouty. Lower Bound for Non-Adaptive Estimation of the Number of Defective Items. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.ISAAC.2019.2,
  author =	{Bshouty, Nader H.},
  title =	{{Lower Bound for Non-Adaptive Estimation of the Number of Defective Items}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.2},
  URN =		{urn:nbn:de:0030-drops-114983},
  doi =		{10.4230/LIPIcs.ISAAC.2019.2},
  annote =	{Keywords: Group Testing, Estimation, Defective Items}
}
Document
Dividing Splittable Goods Evenly and With Limited Fragmentation

Authors: Peter Damaschke

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)


Abstract
A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares of at most F pieces. We call F the fragmentation. For F=1 we can solve the max-min and min-max problems in linear time. The case F=2 has neat formulations and structural characterizations in terms of weighted graphs. Here we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if m>=n-1, and a solution always exists in this case. Moreover, case F=2 is fixed-parameter tractable in the parameter 2m-n. The results also give rise to various open problems.

Cite as

Peter Damaschke. Dividing Splittable Goods Evenly and With Limited Fragmentation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{damaschke:LIPIcs.MFCS.2017.9,
  author =	{Damaschke, Peter},
  title =	{{Dividing Splittable Goods Evenly and With Limited Fragmentation}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.9},
  URN =		{urn:nbn:de:0030-drops-80579},
  doi =		{10.4230/LIPIcs.MFCS.2017.9},
  annote =	{Keywords: packing, load balancing, weighted graph, linear-time algorithm, parameterized algorithm}
}
  • Refine by Author
  • 2 Damaschke, Peter
  • 1 Bshouty, Nader H.

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Probabilistic computation

  • Refine by Keyword
  • 1 Defective Items
  • 1 Estimation
  • 1 Group Testing
  • 1 Patrolling
  • 1 Periodic scheduling
  • Show More...

  • Refine by Type
  • 3 document

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

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail