Narrow Results

In this paper, we explore the power of quantum computers with restricted transition amplitudes. In 1997 Adleman, DeMarrais, and Huang showed that quantum Turing machines (QTMs) with the amplitudes from are computationally equivalent to ones with the polynomial-time computable amplitudes as machines implementing bounded-error polynomial-time algorithms. We show that QTMs with the amplitudes from is polynomial-time equivalent to deterministic Turing machines as machines implementing exact algorithms, i.e., algorithms that output correct answers with certainty. By extending this result, it is shown that exact quantum computers with rational biased coins are equivalent to classical computers. Moreover, we discuss the computational power of exact quantum computers with multiple types of coins. We also show that, from the viewpoint of zero-error polynomial-time algorithms, is not more powerful than as the set of amplitudes taken by QTMs; however, it is sufficient to solve the factoring problem.

Given two simple polygons P and Q we define the weight of a bridge (p,q), with p ∈ ρ(P) and q ∈ ρ(Q), where ρ() denotes the compact region enclosed by the boundary of the polygon, between the two polygons as gd(p,P) + d(p,q) + gd(q,Q), where d(p,q) is the Euclidean distance between the points p and q, and gd(x,X) is the geodesic distance between x and its geodesic furthest neighbor on X. Our problem differs from another version of the problem where the additional restriction of requiring the endpoints of the bridge to be mutually visible was imposed. We show that an optimal bridge always exists such that the endpoints of the bridge lie on the boundaries of the two polygons. Using this critical property, we present an algorithm to find an optimal bridge (of minimum weight) in O(n²log n) time. We present a polynomial time approximation scheme that for any ∊ > 0 generates a bridge with objective function within a factor of 1 + ∊ of the optimal value in O(kn log kn) time, where . An improved polynomial time approximation scheme and algorithms for generalized versions of our problems are also discussed.

Many applications like image processing, data compression or pattern recognition require a covering of a set of n points most often located in the (discrete) plane by rectangles due to specific cost constraints. In this paper we provide exact dynamic programming algorithms for covering point sets by regular rectangles, that have to obey certain boundary conditions, namely all rectangles must have lengths of at least k, which is a prescribed problem parameter. The concrete objective function underlying our optimization problem is the sum of area, circumference and a constant over all rectangles forming a covering. This objective function can be motivated by requirements of numerically solving PDE's by discretization over (adaptive multi-)grids.

More precisely, we propose exact deterministic algorithms for such problems based on a (set theoretic) dynamic programming approach yielding a time bound of O(n²3ⁿ). In a second step this bound is (asymptotically) decreased to O(n⁶2ⁿ) by exploiting some structural features. Finally, a generalization of the problem and its solution methods is discussed for the case of arbitrary (finite) space dimension.

Centralized matching programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs. At the heart of these programs are algorithms to solve kidney exchange problems, which can be modelled as cycle packing problems in a directed graph, involving cycles of length 2, 3, or even longer. Usually, the goal is to maximize the number of transplants, but sometimes the total benefit is maximized by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight in directed graphs. Here we prove the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles. We also present an approximation algorithm and an exact algorithm for the problem of finding a maximum weight exchange involving cycles of bounded length. The exact algorithm has been used to provide optimal solutions to real kidney exchange problems arising from the National Matching Scheme for Paired Donation run by NHS Blood and Transplant, and we describe practical experience based on this collaboration.

Given an undirected graph, a balanced node separator is a set of nodes whose removal splits the graph into connected components of limited size. Balanced node separators are used for graph partitioning, for the construction of graph data structures, and for measuring network reliability. It is NP-hard to decide whether a graph has a balanced node separator of size at most $k$. Therefore, practical algorithms typically try to find small separators in a heuristic fashion. In this paper, we present a branching algorithm that for a given value $k$ either outputs a balanced node separator of size at most $k$ or certifies that $k$ is a valid lower bound. Using this algorithm iteratively for growing values of $k$ allows us to find a minimum balanced node separator. To make this algorithm scalable to real-world (road) networks of considerable size, we first describe pruning rules to reduce the graph size without affecting the minimum balanced separator size. In addition, we prove several structural properties of minimum balanced node separators which are then used to reduce the branching factor and search depth of our algorithm. We experimentally demonstrate the applicability of our algorithm to graphs with thousands of nodes and edges. We showcase the usefulness of having minimum balanced separators for judging the quality of existing heuristics, for improving preprocessing-based route planning techniques on road networks, and for lower bounding important graph parameters. Finally, we discuss how our ideas and methods can also be leveraged to accelerate the heuristic computation of balanced node separators.