On the longest increasing subsequence of a circular list

The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time O(n3/2logn) and storage requirement O(n). It is proved that the expected length μ(n) of the LICS satisfies . Numerical experiments with the algorithm suggest that .     

On exact solutions to the Euclidean bottleneck Steiner tree problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal -time exact algorithm for k=1 and an O(n²)-time algorithm for k=2. Also, we present an optimal -time exact algorithm for any constant k for a special case where there is no edge between Steiner points.     

Greedy algorithms for generalized k-rankings of paths

A k-ranking of a graph is a labeling of the vertices with positive integers 1,2,…,k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let Pn be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of Pn. In this paper we investigate two generalizations of rankings. We first consider bounded (k,s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider kt-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number to be the smallest number of labels that can be used in a (k,s)-ranking and show for n?2, where i=⌊log₂(s)⌋+1. We define the kt-rank number, to be the smallest number of labels that can be used in a kt-ranking. We present a recursive formula that gives the kt-rank numbers for paths, showing for all an−1<j?an where {an} is defined as follows: a₁=1 and an=⌊((t+1)/t)an−1⌋+1.     

Improved deterministic approximation algorithms for Max TSP

We present an O(n³)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n³)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically . Both algorithms improve on the previous bests.     

How much precision is needed to compare two sums of square roots of integers?

In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) be the minimum positive value of where ai and bi are integers not larger than integer n. We prove by an explicit construction that r(n,k)=O(n−2k+3/2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as digits. We also prove that this bound is optimal for a wide range of integers, i.e., r(n,k)=Θ(n−2k+3/2) for fixed k and for those integers in the form of and , where n^′ is any integer satisfied the form and i is any integer in [0,k−1]. We finally show that for k=2 and any n, this bound is also optimal, i.e., r(n,2)=Θ(n−7/2).     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

Quantum lower bounds for the Goldreich-Levin problem

At the heart of the Goldreich-Levin theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, on input x, returns a bit that is biased towards a⋅x (the modulo two inner product of a with x) in the following sense. For a random x, the probability that IP(x)=a⋅x is at least . The EQ oracle, on input x, returns a bit specifying whether or not x=a. It has been shown that a quantum algorithm can solve this problem with O(1/?) IP and EQ queries, whereas any classical algorithm requires Ω(n/?²) such queries. Also, the quantum algorithm requires only O(n/?) auxiliary one- and two-qubit gates in addition to its queries. We show that the above quantum algorithm is optimal in terms of both EQ and IP queries. Specifically, Ω(1/?) EQ queries are necessary, and Ω(1/?) IP queries are necessary if the number of EQ queries is .     

Uniform metrical task systems with a limited number of states

We give a randomized algorithm (the “Wedge Algorithm”) of competitiveness for any metrical task system on a uniform space of k points, for any k?2, where , the kth harmonic number. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 10⁸. The algorithm is better by a factor of 2 if k<47.     

Narrowing power vs efficiency in synchronous set agreement: Relationship, algorithms and lower bound

The k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most k different values are decided. It has been shown that any algorithm that solves the k-set agreement problem in synchronous systems that can suffer up to t crash failures requires rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after rounds, where f is the number of actual crashes in a run (0≤f≤t).This paper explores a new direction to solve the k-set agreement problem in a synchronous system. It considers that the system is enriched with base objects (denoted has [m,?]_SA objects) that allow solving the ?-set agreement problem in a set of m processes (m<n). The paper makes several contributions. It first proposes a synchronous k-set agreement algorithm that benefits from such underlying base objects. This algorithm requires rounds, more precisely, rounds, where . The paper then shows that this bound, that involves all the parameters that characterize both the problem (k) and its environment (t, m and ?), is a lower bound. The proof of this lower bound sheds additional light on the deep connection between synchronous efficiency and asynchronous computability. Finally, the paper extends its investigation to the early deciding case. It presents a k-set agreement algorithm that directs the processes to decide and stop by round . These bounds generalize the bounds previously established for solving the k-set agreement problem in pure synchronous systems.     

Finding shortest safari routes in simple polygons

Let P be a simple polygon, and let be a set of disjoint convex polygons inside P, each sharing one edge with P. The safari route problem asks for a shortest route inside P that visits each polygon in . In this paper, we first present a dynamic programming algorithm with running time O(n³) for computing the shortest safari route in the case that a starting point on the route is given, where n is the total number of vertices of P and polygons in . (Ntafos in [Comput. Geom. 1 (1992) 149-170] claimed a more efficient solution, but as shown in Appendix A of this paper, the time analysis of Ntafos' algorithm is erroneous and no time bound is guaranteed for his algorithm.) The restriction of giving a starting point is then removed by a brute-force algorithm, which requires O(n⁴) time. The solution of the safari route problem finds applications in watchman routes under limited visibility.