Search Results

Documents authored by Bärtschi, Andreas

Document
DOI: 10.4230/LIPIcs.MFCS.2018.56
Collective Fast Delivery by Energy-Efficient Agents

Authors: Andreas Bärtschi, Daniel Graf, and Matús Mihalák

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths). The agents have to deliver a single item from a given source node s to a given target node t. The agents can move along the edges of the graph, starting at time 0, with respect to the following: Each agent i has a weight omega_i that defines the rate of energy consumption while travelling a distance in the graph, and a velocity upsilon_i with which it can move. We are interested in schedules (operating the k agents) that result in a small delivery time T (time when the item arrives at t), and small total energy consumption E. Concretely, we ask for a schedule that: either (i) Minimizes T, (ii) Minimizes lexicographically (T,E) (prioritizing fast delivery), or (iii) Minimizes epsilon * T + (1-epsilon)* E, for a given epsilon in (0,1). We show that (i) is solvable in polynomial time, and show that (ii) is polynomial-time solvable for uniform velocities and solvable in time O(n+k log k) for arbitrary velocities on paths, but in general is NP-hard even on planar graphs. As a corollary of our hardness result, (iii) is NP-hard, too. We show that there is a 2-approximation algorithm for (iii) using a single agent.
Cite as

Andreas Bärtschi, Daniel Graf, and Matús Mihalák. Collective Fast Delivery by Energy-Efficient Agents. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:LIPIcs.MFCS.2018.56,
  author =	{B\"{a}rtschi, Andreas and Graf, Daniel and Mihal\'{a}k, Mat\'{u}s},
  title =	{{Collective Fast Delivery by Energy-Efficient Agents}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{56:1--56:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.56},
  URN =		{urn:nbn:de:0030-drops-96381},
  doi =		{10.4230/LIPIcs.MFCS.2018.56},
  annote =	{Keywords: delivery, mobile agents, time/energy optimization, complexity, algorithms}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.2
Truthful Mechanisms for Delivery with Agents

Authors: Andreas Bärtschi, Daniel Graf, and Paolo Penna

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
We study the game-theoretic task of selecting mobile agents to deliver multiple items on a network. An instance is given by $m$ packages (physical objects) which have to be transported between specified source-target pairs in an undirected graph, and $k$ mobile heterogeneous agents, each being able to transport one package at a time. Following a recent model [Baertschi et al. 2017], each agent i has a different rate of energy consumption per unit distance traveled, i.e., its weight. We are interested in optimizing or approximating the total energy consumption over all selected agents. Unlike previous research, we assume the weights to be private values known only to the respective agents. We present three different mechanisms which select, route and pay the agents in a truthful way that guarantees voluntary participation of the agents, while approximating the optimum energy consumption by a constant factor. To this end, we analyze a previous structural result and an approximation algorithm given in [Baertschi et al. 2017]. Finally, we show that for some instances in the case of a single package, the sum of the payments can be bounded in terms of the optimum.
Cite as

Andreas Bärtschi, Daniel Graf, and Paolo Penna. Truthful Mechanisms for Delivery with Agents. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:OASIcs.ATMOS.2017.2,
  author =	{B\"{a}rtschi, Andreas and Graf, Daniel and Penna, Paolo},
  title =	{{Truthful Mechanisms for Delivery with Agents}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{2:1--2:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.2},
  URN =		{urn:nbn:de:0030-drops-78891},
  doi =		{10.4230/OASIcs.ATMOS.2017.2},
  annote =	{Keywords: delivery, agent, energy optimization, approximation mechanism, frugality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.10
Energy-Efficient Delivery by Heterogeneous Mobile Agents

Authors: Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We consider the problem of delivering m messages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes of the graph. Each edge has a designated length and each agent consumes energy proportional to the distance it travels in the graph. We are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights w_i). To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages). We first show that the delivery problem can be 2-approximated without collaborating and that this is best possible, i.e., we show that the benefit of collaboration is 2 in general. We also show that the benefit of collaboration for a single message is 1 / log 2 which is approximately 1.44. Planning turns out to be NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they additionally have uniform weights. Finally, we give a polynomial-time c-approximation for message delivery with unit capacities.
Cite as

Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna. Energy-Efficient Delivery by Heterogeneous Mobile Agents. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:LIPIcs.STACS.2017.10,
  author =	{B\"{a}rtschi, Andreas and Chalopin, J\'{e}r\'{e}mie and Das, Shantanu and Disser, Yann and Graf, Daniel and Hackfeld, Jan and Penna, Paolo},
  title =	{{Energy-Efficient Delivery by Heterogeneous Mobile Agents}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.10},
  URN =		{urn:nbn:de:0030-drops-70233},
  doi =		{10.4230/LIPIcs.STACS.2017.10},
  annote =	{Keywords: message delivery, mobile agents, energy optimization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.160
Conflict-free Chromatic Art Gallery Coverage

Authors: Andreas Bärtschi and Subhash Suri

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We consider a chromatic variant of the art gallery problem, where each guard is assigned one of k distinct colors. A placement of such colored guards is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. What is the smallest number k(n) of colors that ensure a conflict-free covering of all n-vertex polygons? We call this the conflict-free chromatic art gallery problem. The problem is motivated by applications in distributed robotics and wireless sensor networks where colors indicate the wireless frequencies assigned to a set of covering "landmarks" in the environment so that a mobile robot can always communicate with at least one landmark in its line-of-sight range without interference. Our main result shows that k(n) is O(log n) for orthogonal and for monotone polygons, and O(log^2 n) for arbitrary simple polygons. By contrast, if all guards visible from each point must have distinct colors, then k(n)is Omega(n) for arbitrary simple polygons and Omega(sqrt(n)) for orthogonal polygons, as shown by Erickson and LaValle [Proc. of RSS 2011].
Cite as

Andreas Bärtschi and Subhash Suri. Conflict-free Chromatic Art Gallery Coverage. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 160-171, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:LIPIcs.STACS.2012.160,
  author =	{B\"{a}rtschi, Andreas and Suri, Subhash},
  title =	{{Conflict-free Chromatic Art Gallery Coverage}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{160--171},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.160},
  URN =		{urn:nbn:de:0030-drops-33952},
  doi =		{10.4230/LIPIcs.STACS.2012.160},
  annote =	{Keywords: art gallery problem, conflict-free coloring, visibility}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact