Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer

Show simple item record Liu, K en Dinneen, Michael en 2020-01-10T02:29:23Z en 2019-06 en
dc.identifier.issn 1178-3540 en
dc.identifier.uri en
dc.description.abstract This paper describes a new approach for finding an approximate Euclidean shortest path with additional constraints, which we call a multi-criterion shortest path, between two given points that avoids vertical obstacles in a three-dimensional space. Currently, there does not exist any polynomial-time algorithm that solves this problem exactly, even without additional constraints. Furthermore, existing approximation algorithms mostly focus on reducing the running time at the expense of the accuracy. Here, we aim at increasing the accuracy of an approximate shortest path. To this end, our new algorithm is based on geometric principles to determine all obstacle segments and partial obstacle segments that are visible to each other. Using this information, we employ Mixed Integer Linear Programming to compute an approximate shortest path between two given points. We test our algorithm on a number of test cases and find that our method returns approximate shortest paths that are shorter than those returned by other currently available algorithms. Moreover, our method is more flexible since it allows users to define additional constraints or criteria in exploring different types of optimal paths. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri en
dc.title Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer en
dc.type Report en
pubs.volume CDMTCS-538 en
dc.rights.holder Copyright: The author en
dc.rights.accessrights en
pubs.subtype Technical Report en
pubs.elements-id 773842 en Science en School of Computer Science en
pubs.record-created-at-source-date 2019-06-06 en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace