Optimal algorithms for the average-constrained maximum-sum segment problem

Given a real number sequence A=(a₁,a₂,…,an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A(i,j)=(ai,ai+1,…,aj) that maximizes _∑i?k?jak subject to . In this paper, we give an O(n)-time algorithm for the case where the average upper bound is ineffective, i.e., U=∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω(nlogn) even if the average lower bound is ineffective, i.e., L=−∞.     

Flying over a polyhedral terrain

We consider the problem of computing shortest paths in three-dimensions in the presence of a single-obstacle polyhedral terrain, and present a new algorithm that for any p?1, computes a (c+ε)-approximation to the Lp-shortest path above a polyhedral terrain in time and O(nlogn) space, where n is the number of vertices of the terrain, and c=²(p−1)/p. This leads to a FPTAS for the problem in L₁ metric, a -factor approximation algorithm in Euclidean space, and a 2-approximation algorithm in the general Lp metric.     

Improved generalized Atkin algorithm for computing square roots in finite fields

Recently, S. Müller developed a generalized Atkin algorithm for computing square roots, which requires two exponentiations in finite fields GF(q) when . In this paper, we present a simple improvement to it and the improved algorithm requires only one exponentiation for half of squares in finite fields GF(q) when . Furthermore, in finite fields GF(pm), where and m is odd, we reduce the complexity of the algorithm from O(m³log³p) to O(m²log²p(logm+logp)) using the Frobenius map and normal basis representation.     

Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme

We propose cryptanalysis of the First Domingo-Ferrer's algebraic privacy homomorphism where n=pq. We show that the scheme can be broken by (d+1) known plaintexts in O(d³log²n) time. Even when the modulus n is kept secret, it can be broken by 2(d+1) known plaintexts in O(d⁴logdn+d³log²n+?(m)) time with overwhelming probability.     

Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations

It has been shown that for every perfect matching M of the d-dimensional n-vertex hypercube, d?2, n=d², there exists a second perfect matching M^′ such that the union of M and M^′ forms a Hamiltonian circuit of the d-dimensional hypercube. We prove a generalization of a special case of this result when there are two dimensions that do not get used by M. It is known that the number Md of perfect matchings of the d-dimensional hypercube satisfies and, in particular, (2d/n)^n/2(n/2)!?Md?(d!)^n/(2d). It has also been shown that the number Hd of Hamiltonian circuits of the hypercube satisfies 1?limd→∞(logHd)/(logMd)?2. We finally strengthen this result to a nearly tight bound ((dlog2/(eloglogd))(1−on(1)))?Hd?(d!)^n/(2d)((d−1)!)^n/(2(d−1))/2 proving that limd→∞(logHd)/(logMd)=2. This means that the bound Hd?Md is improved to a nearly tight , so the number of Hamiltonian circuits in the hypercube is nearly quadratic in the number of perfect matchings. The proofs are based on a result for graphs that are the Cartesian product of squares and arbitrary bipartite regular graphs that have a Hamiltonian cycle. We also study a labeling scheme related to matchings.     

Super-connected and super-arc-connected Cartesian product of digraphs

We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained:

(i)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=κ(Di) for i=1,2, then D₁×D₂ is super-κ if and only if ,

(ii)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=λ(Di) for i=1,2, then D₁×D₂ is super-λ if and only if ,

where λ(D)=δ(D)=1, denotes the complete digraph of order n and n?2.     

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).     

On the complexity of finding balanced oneway cuts

A bisection of an n-vertex graph is a partition of its vertices into two sets S and T, each of size n/2. The bisection cost is the number of edges connecting the two sets. In directed graphs, the cost is the number of arcs going from S to T. Finding a minimum cost bisection is NP-hard for both undirected and directed graphs. For the undirected case, an approximation of ratio O(log²n) is known. We show that directed minimum bisection is not approximable at all. More specifically, we show that it is NP-hard to tell whether there exists a directed bisection of cost 0, which we call oneway bisection. In addition, we study the complexity of the problem when some slackness in the size of S is allowed, namely, (1/2−ε)n?|S|?(1/2+ε)n. We show that the problem is solvable in polynomial time when , and provide evidence that the problem is not solvable in polynomial time when ε=o(1/(logn)⁴).     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

Edge-fault-tolerant diameter and bipanconnectivity of hypercubes

Let n(?3) be a given integer and . And let Qn be an n-dimensional hypercube and F⊂E(Qn), such that every vertex of the graph Qn−F is incident with at least two edges. Assume x and y are any two vertices with Hamming distance H(x,y)=h. In this paper, we obtain the following results: (1) If h?2 and |F|?min{n+h−1,2n−5}, then in Qn−F there exists an xy-path of each length l∈Ωh+2, and the upper bound n+h−1 on |F| is sharp when 2?h?n−4, and the upper bound 2n−5 on |F| is sharp when n−4?h?n−1 and h=2. (2) If |F|?2n−5, then in Qn−F there exists an xy-path of each length l∈Ωs, where s=h if n−1?h?n, and s=h+2 if n−4?h?n−2 and h?2, and s=h+4 otherwise. Hence, the diameter of the graph Qn−F is n. Our results improve some previous results.     

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.     

On the Euler sequence spaces which include the spaces ?p and ?∞ I

In the present paper, we introduce the Euler sequence space consisting of all sequences whose Euler transforms of order r are in the space ?_p of non-absolute type which is the BK-space including the space ?_p and prove that the spaces and ?_p are linearly isomorphic for 1 ? p ? ∞. Furthermore, we give some inclusion relations concerning the space . Finally, we determine the α-, β- and γ-duals of the space for 1 ? p ? ∞ and construct the basis for the space , where 1 ? p < ∞.     

A combinatorial property on angular orders of plane point sets

We study the following combinatorial property of point sets in the plane: For a set S of n points in general position and a point p∈S consider the points of S−p in their angular order around p. This gives a star-shaped polygon (or a polygonal path) with p in its kernel. Define c(p) as the number of convex angles in this star-shaped polygon around p, and c(S) as the sum of all c(p), for p∈S. We show that for every point set S, c(S) is always at least . This bound is shown to be almost tight. Consequently, every set of n points admits a star-shaped polygonization with at least convex angles.     

Probabilistic integer sorting

We introduce a probabilistic sequential algorithm for stable sorting n uniformly distributed keys in an arbitrary range. The algorithm runs in linear time and sorts all but a very small fraction of the input sequences; the best previously known bound was . An EREW PRAM extension of this sequential algorithm sorts in O((n/p+lgp)lgn/lg(n/p+lgn)) time using p?n processors under the same probabilistic conditions. For a CRCW PRAM we improve upon the probabilistic bound of obtained by Rajasekaran and Sen to derive a bound. Additionally, we present experimental results for the sequential algorithm that establish the practicality of our method.     

Finding bipartite subgraphs efficiently

Polynomial algorithms are given for the following two problems:

•

given a graph with n vertices and m edges, find a complete balanced bipartite subgraph Kq,q with ,

•

given a graph with n vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether O(n²/lnn) vertices.

The first algorithm can be modified to have running time linear in m and find a Kq^′,q^′ with q^′=⌊q/5⌋. Previous proofs of the existence of such objects, due to K?vári, Sós and Turán (1954) [10], Chung, Erd?s and Spencer (1983) [5], Bublitz (1986) [4] and Tuza (1984) [13] were non-constructive.     

A running time analysis of an Ant Colony Optimization algorithm for shortest paths in directed acyclic graphs

In this paper, we prove polynomial running time bounds for an Ant Colony Optimization (ACO) algorithm for the single-destination shortest path problem on directed acyclic graphs. More specifically, we show that the expected number of iterations required for an ACO-based algorithm with n ants is for graphs with n nodes and m edges, where ρ is an evaporation rate. This result can be modified to show that an ACO-based algorithm for One-Max with multiple ants converges in expected iterations, where n is the number of variables. This result stands in sharp contrast with that of Neumann and Witt, where a single-ant algorithm is shown to require an exponential running time if ρ=O(n−1−ε) for any ε>0.     

New instability results for high-dimensional nearest neighbor search

Consider a dataset of n(d) points generated independently from Rd according to a common p.d.f. fd with support(fd)=d[0,1] and sup{fd(Rd)} growing sub-exponentially in d. We prove that: (i) if n(d) grows sub-exponentially in d, then, for any query point and any ?>0, the ratio of the distance between any two dataset points and is less that 1+? with probability →1 as d→∞; (ii) if n(d)>d[4(1+?)] for large d, then for all (except a small subset) and any ?>0, the distance ratio is less than 1+? with limiting probability strictly bounded away from one. Moreover, we provide preliminary results along the lines of (i) when .