5 Search Results for "Bärtschi, Andreas"

Document
DOI: 10.4230/LIPIcs.SAT.2024.29
Quantum Circuit Mapping Based on Incremental and Parallel SAT Solving

Authors: Jiong Yang, Yaroslav A. Kharkov, Yunong Shi, Marijn J. H. Heule, and Bruno Dutertre

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
Quantum Computing (QC) is a new computational paradigm that promises significant speedup over classical computing in various domains. However, near-term QC faces numerous challenges, including limited qubit connectivity and noisy quantum operations. To address the qubit connectivity constraint, circuit mapping is required for executing quantum circuits on quantum computers. This process involves performing initial qubit placement and using the quantum SWAP operations to relocate non-adjacent qubits for nearest-neighbor interaction. Reducing the SWAP count in circuit mapping is essential for improving the success rate of quantum circuit execution as SWAPs are costly and error-prone. In this work, we introduce a novel circuit mapping method by combining incremental and parallel solving for Boolean Satisfiability (SAT). We present an innovative SAT encoding for circuit mapping problems, which significantly improves solver-based mapping methods and provides a smooth trade-off between compilation quality and compilation time. Through comprehensive benchmarking of 78 instances covering 3 quantum algorithms on 2 distinct quantum computer topologies, we demonstrate that our method is 26× faster than state-of-the-art solver-based methods, reducing the compilation time from hours to minutes for important quantum applications. Our method also surpasses the existing heuristics algorithm by 26% in SWAP count.
Cite as

Jiong Yang, Yaroslav A. Kharkov, Yunong Shi, Marijn J. H. Heule, and Bruno Dutertre. Quantum Circuit Mapping Based on Incremental and Parallel SAT Solving. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.SAT.2024.29,
  author =	{Yang, Jiong and Kharkov, Yaroslav A. and Shi, Yunong and Heule, Marijn J. H. and Dutertre, Bruno},
  title =	{{Quantum Circuit Mapping Based on Incremental and Parallel SAT Solving}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.29},
  URN =		{urn:nbn:de:0030-drops-205517},
  doi =		{10.4230/LIPIcs.SAT.2024.29},
  annote =	{Keywords: Quantum computing, Quantum compilation, SAT solving, Incremental solving, Parallel solving}
}
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}
}
  • Refine by Author
  • 4 Bärtschi, Andreas
  • 3 Graf, Daniel
  • 2 Penna, Paolo
  • 1 Chalopin, Jérémie
  • 1 Das, Shantanu
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Quantum computing
  • 1 Computing methodologies → Artificial intelligence
  • 1 Software and its engineering → Compilers
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 delivery
  • 2 energy optimization
  • 2 mobile agents
  • 1 Incremental solving
  • 1 Parallel solving
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2017
  • 1 2012
  • 1 2018
  • 1 2024

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 Imprint Privacy Contact