Amaury Van Bemten, Jochen W. Guck, Carmen Mas Machuca, Wolfgang Kellerer
2019-03-01
The shortest path (SP) and shortest paths tree (SPT) problems arise both as direct applications and as subroutines of overlay algorithms solving more complex problems such as the constrained shortest path (CSP) or the constrained minimum Steiner tree (CMST) problems. Often, such algorithms do not use the result of an SP subroutine if its total cost is greater than a given bound. For example, for delay-constrained problems, paths resulting from a least-delay SP run and whose delay is greater than the delay constraint of the original problem are not used by the overlay algorithm to construct its solution. As a result of the existence of these bounds, and because the Dijkstra SP algorithm discovers paths in increasing order of cost, we can terminate the SP search earlier, i.e., once it is known that paths with a greater total cost will not be considered by the overlay algorithm. This early termination allows to reduce the runtime of the SP subroutine, thereby reducing the runtime of the overlay algorithm without impacting its final result. We refer to this adaptation of Dijkstra for centralized implementations as bounded Dijkstra (BD). On the example of CSP algorithms, we confirm the usefulness of BD by showing that it can reduce the runtime of some algorithms by 75% on average.
Lorenz Hübschle-Schneider, Peter Sanders
2019-03-01
Data structures for efficient sampling from a set of weighted items are an important building block of many applications. However, few parallel solutions are known. We close many of these gaps both for shared-memory and distributed-memory machines. We give efficient, fast, and practicable algorithms for sampling single items, k items with/without replacement, permutation, subset sampling, and reservoir sampling. Our output sensitive algorithm for sampling with replacement also improves the state of the art for sequential algorithms.
Rohan Kodialam
2019-02-28
We consider a variant of the classic Ski Rental online algorithm with applications to machine learning. In our variant, we allow the skier access to a black-box machine-learning algorithm that provides an estimate of the probability that there will be at most a threshold number of ski-days. We derive a class of optimal randomized algorithms to determine the strategy that minimizes the worst-case expected competitive ratio for the skier given a prediction from the machine learning algorithm,and analyze the performance and robustness of these algorithms.
Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, Seyon Sivarajah
2019-02-21
We introduce a new architecture-agnostic methodology for mapping abstract quantum circuits to realistic quantum computing devices with restricted qubit connectivity, as implemented by Cambridge Quantum Computing's tket compiler. We present empirical results showing the effectiveness of this method in terms of reducing two-qubit gate depth and two-qubit gate count, compared to other implementations.
Jamie Morgenstern, Samira Samadi, Mohit Singh, Uthaipon Tantipongpipat, Santosh Vempala
2019-02-28
We model "fair" dimensionality reduction as an optimization problem. A central example is the fair PCA problem: the input data is divided into
groups, and the goal is to find a single -dimensional representation for all groups for which the maximum variance (or minimum reconstruction error) is optimized for all groups in a fair (or balanced) manner, e.g., by maximizing the minimum variance over the groups of the projection to a -dimensional subspace. This problem was introduced by Samadi et al. (2018) who gave a polynomial-time algorithm which, for groups, returns a -dimensional solution of value at least the best -dimensional solution. We give an exact polynomial-time algorithm for groups. The result relies on extending results of Pataki (1998) regarding rank of extreme point solutions to semi-definite programs. This approach applies more generally to any monotone concave function of the individual group objectives. For groups, our results generalize to give a -dimensional solution with objective value as good as the optimal -dimensional solution for arbitrary in polynomial time. Using our extreme point characterization result for SDPs, we give an iterative rounding framework for general SDPs which generalizes the well-known iterative rounding approach for LPs. It returns low-rank solutions with bounded violation of constraints. We obtain a -dimensional projection where the violation in the objective can be bounded additively in terms of the top -singular values of the data matrices. We also give an exact polynomial-time algorithm for any fixed number of groups and target dimension via the algorithm of Grigoriev and Pasechnik (2005). In contrast, when the number of groups is part of the input, even for target dimension , we show this problem is NP-hard.
Riko Jacob, Gerth Stølting Brodal
2019-02-28
In this article, we determine the amortized computational complexity of the planar dynamic convex hull problem by querying. We present a data structure that maintains a set of n points in the plane under the insertion and deletion of points in amortized O(log n) time per operation. The space usage of the data structure is O(n). The data structure supports extreme point queries in a given direction, tangent queries through a given point, and queries for the neighboring points on the convex hull in O(log n) time. The extreme point queries can be used to decide whether or not a given line intersects the convex hull, and the tangent queries to determine whether a given point is inside the convex hull. We give a lower bound on the amortized asymptotic time complexity that matches the performance of this data structure.
Callum Schofield, Jingbo B. Wang, Yuying Li
2019-02-28
Large scale complex systems, such as social networks, electrical power grid, database structure, consumption pattern or brain connectivity, are often modeled using network graphs. Valuable insight can be gained by measuring the similarity between network graphs in order to make quantitative comparisons. Since these networks can be very large, scalability and efficiency of the algorithm are key concerns. More importantly, for graphs with unknown labeling, this graph similarity problem requires exponential time to solve using existing algorithms. In this paper, we propose a quantum walk inspired algorithm, which provides a solution to the graph similarity problem without prior knowledge on graph labeling. This algorithm is capable of distinguishing between minor structural differences, such as between strongly regular graphs with the same parameters. The algorithm has polynomial complexity, scaling with
.
Hannaneh Akrami, Kurt Mehlhorn, Tommy Odland
2019-02-28
When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form of \emph{security}, which will be collected if the lender defaults. Accounts can be secured by several securities and a security can be used for several accounts. The goal is to fractionally assign the securities to the accounts so as to balance the risk. This situation can be modelled by a bipartite graph. We have a set
of securities and a set of accounts. Each security has a \emph{value} and each account has an \emph{exposure} . If a security can be used to secure an account , we have an edge from to . Let be part of security 's value used to secure account . We are searching for a maximum flow that send at most units out of node and at most units into node . Then is the unsecured part of account . We are searching for the maximum flow that minimizes .
Barbara Covella, Fabrizio Frati, Maurizio Patrignani
2019-02-28
In this paper, we study the area requirements of planar straight-line orthogonal drawings of ternary trees. We prove that every ternary tree admits such a drawing in sub-quadratic area. Further, we present upper bounds, the outcomes of an experimental evaluation, and a conjecture on the area requirements of planar straight-line orthogonal drawings of complete ternary trees. Finally, we present a polynomial lower bound on the length of the minimum side of any planar straight-line orthogonal drawing of a complete ternary tree.
Pavel S. Ruzankin
2019-02-07
We suggest a new non-recursive algorithm for constructing a binary search tree given an array of numbers. The algorithm has
time and memory complexity if the given array of numbers is sorted. The resulting tree is of minimal height and can be transformed to a complete binary search tree (retaining minimal height) with time and memory. The algorithm allows simple and effective parallelization.
