Data Structures And Algorithms
Bounded Dijkstra (BD): Search Space Reduction for Expediting Shortest Path Subroutines (1903.00436v1)
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.
Parallel Weighted Random Sampling (1903.00227v1)
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.
Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions (1903.00092v1)
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.
On the qubit routing problem (1902.08091v2)
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.
Fair Dimensionality Reduction and Iterative Rounding for SDPs (1902.11281v1)
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, returns a
-dimensional solution of value at least the best
groups, our results generalize to give a
-dimensional solution with objective value as good as the optimal
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
-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.
Dynamic Planar Convex Hull (1902.11169v1)
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.
Quantum walk inspired algorithm for graph similarity and isomorphism (1902.11105v1)
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
.
Ratio-Balanced Maximum Flows (1902.11047v1)
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
be part of security
and at most
. Then
is the unsecured part of account
.
On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees (1902.11044v1)
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.
A fast algorithm for constructing balanced binary search trees (1902.02499v3)
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