On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.     

Efficient randomized generation of optimal algorithms for multiplication in certain finite fields

LetN _max(q) denote the maximum number of points of an elliptic curve over F _q . Given a prime powerq=p ^f and an integern satisfying 1/2q+1<n(N _max(q)–2)/2, we present an algorithm which on inputq andn produces an optimal bilinear algorithm of length 2n for multiplication in F _q ⁿ /F _q . The algorithm takes roughlyO(q ⁴+n ⁴logq) F _q -operations or equivalentlyO((q ⁴+n ⁴logq)f ²log² p) bit-operations to compute the output data.     

A note on a problem on ω-limit sets of N–dimensional skew-product maps

In 2003, Balibrea et al. stated the problem of finding a skew-product map G on 𝕀³ holding ω _G ={0}×𝕀²=ω _G (x, y, z) for any (x, y, z)∈𝕀³, x≠0. We present a method for constructing skew-product maps F on 𝕀 ⁿ⁺¹ holding ω _F ={0}×𝕀 ⁿ =ω _F (x ₁, x ₂, …, x _n+1), (x ₁, x ₂, …, x _n+1)∈𝕀 ⁿ⁺¹, x ₁≠0.     

Stochastic adaptive pole-zero assignment with convergence analysis

The adaptive control u_n is designed for the stochastic system A(z)y_n+1 = B(z)u_n+C(z)w_n+1 with unknown constant matrix coefficients in the polynomials A(z), B(z) and C(z) in the shift-back operator with the purposes that (1) the unknown matrices are strongly consistently estimated and (2) the poles and zeros are replaced in such a way that the system itself is transferred to A⁰(z)y_n+1 = B⁰(z)u_n⁰+_n+1 with given A⁰(z), B⁰(z) and u_n⁰ so that the pole-zero assignment error {_n+1} is minimized. The problem of adaptive pole-zero assignment combined with tracking is also considered in this paper. Conditions used are imposed only on A(z), B(z) and C(z).     

Finding the Extrema of a Distributed Multiset

We consider the problem of finding the extrema of a distributed multiset in a ring, that is, of determining the minimum and the maximum values,x_minandx_max, of a multisetX= {x₀,x₂, ...,x_n−1} whose elements are drawn from a totally ordered universeUand stored at thenentities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and it has complexity Θ(n²) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved inO((c+ logn) ·n) bits andO(n·c·x^1/c) time for any integerc> 0, wherex= Max{|x_min|, |x_max|}. The previous solutions requiredO(n²) bits and the same amount of time. Based on these results, we also present a bit-optimal solution to the problem of finding the multiplicity of the extrema.     

Computing multiple pitchfork bifurcation points

A point (x*,λ*) is called apitchfork bifurcation point of multiplicityp≥1 of the nonlinear systemF(x, λ)=0,F:ℝⁿ×ℝ¹→ℝⁿ, if rank∂ _xF(x*, λ*)=n−1, and if the Ljapunov-Schmidt reduced equation has the normal formg(ξ, μ)=±ξ ²⁺ p±μξ=0. It is shown that such points satisfy a minimally extended systemG(y)=0,G:ℝ ⁿ⁺²→ℝⁿ⁺² the dimensionn+2 of which is independent ofp. For solving this system, a two-stage Newton-type method is proposed. Some numerical tests show the influence of the starting point and of the bordering vectors used in the definition of the extended system on the behavior of the iteration.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

Algorithms for dense graphs and networks on the random access computer

We improve upon the running time of several graph and network algorithms when applied to dense graphs. In particular, we show how to compute on a machine with word size = (logn) a maximal matching in ann-vertex bipartite graph in timeO(n ²+n ^2.5/)=O(n ^2.5/logn), how to compute the transitive closure of a digraph withn vertices andm edges in timeO(n ²+nm/), how to solve the uncapacitated transportation problem with integer costs in the range [O.C] and integer demands in the range [–U.U] in timeO ((n ³ (log log/logn)^1/2+n² logU) lognC), and how to solve the assignment problem with integer costs in the range [O.C] in timeO(n ^2.5 lognC/(logn/loglogn)^1/4).Assuming a suitably compressed input, we also show how to do depth-first and breadth-first search and how to compute strongly connected components and biconnected components in timeO(n+n ²/), and how to solve the single source shortest-path problem with integer costs in the range [O.C] in time0 (n ²(logC)/logn). For the transitive closure algorithm we also report on the experiences with an implementation.Most of this research was carried out while both authors worked at the Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, Germany. The research was supported in part by ESPRIT Project No. 3075 ALCOM. The first author acknowledges support also from NSERC Grant No. OGPIN007.     

Approximation algorithms for DNF under distributions with limited independence

In this paper we investigate the problem of approximating the fraction of truth assignments that satisfy a Boolean formula with some restricted form of DNF under distributions with limited independence between random variables. LetF be a DNF formula onn variables withm clauses in which each literal appears at most once. We prove that ifD is [k logm]-wise independent, then |Pr _D [F]-Pr _U [F]| ≤ , whereU denotes the uniform distribution and Pr _D [F] denotes the probability thatF is satisfied by a truth assignment chosen according to distributionD (similarly for Pr _U [F]). Using the result, we also derive the following: For formulas satisfying the restriction described above and for any constantc, there exists a probability distributionD, with size polynomial in logn andm, such that |Pr _D [F] - Pr _U [F]| ≤c holds.     

Parallel Algorithms for Maximal Acyclic Sets

Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in time with O(n ² ) processors on an EREW PRAM. Received July 3, 1995; revised April 1, 1996.     

An algorithm for determining an opaque minimal forest of a convex polygon

Let P be a convex polygon with n vertices in the Euclidean plane. An ‘opaque forest’ for P, denoted F(P), is a finite set of line segments inside or on P so that every line intersecting P also intersects at least one member of F(P). We give an algorithm which computes an opaque minimal (in the L₂ sense) forest, F¹(P), in O(n⁶) time using O(n²) space.     

Geometry Helps in Bottleneck Matching and Related Problems

Let A and B be two sets of n objects in \reals ^d , and let Match be a (one-to-one) matching between A and B . Let min(Match ), max(Match ), and Σ(Match) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of Match , respectively. Bottleneck matching— a matching that minimizes max(Match )— is suggested as a convenient way for measuring the resemblance between A and B . Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is roughly O(n ^1.5 ) . For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n ^1.5 log n ) . A semidynamic data structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion is considered. When A and B are point-sets in the plane, an O(n ⁵ log n) -time algorithm for determining whether for some translated copy the resemblance gets below a given ρ is presented, thus improving the previous result of Alt, Mehlhorn, Wagener, and Welzl by a factor of almost n . This result is used to compute the smallest such ρ in time O(n ⁵ log ² n ) , and an efficient approximation scheme for this problem is also given. The uniform matching problem (also called the balanced assignment problem, or the fair matching problem) is to find Match ^* _U , a matching that minimizes max (Match)-min(Match) . A minimum deviation matching Match ^* _D is a matching that minimizes (1/n)Σ(Match) - min(Match) . Algorithms for computing Match ^* _U and Match ^* _D in roughly O(n ^10/3 ) time are presented. These algorithms are more efficient than the previous O(n ⁴ ) -time algorithms of Martello, Pulleyblank, Toth, and de Werra, and of Gupta and Punnen, who studied these problems for general bipartite graphs. Received October 21, 1997; revised July 16, 1998.     

Finding extrema with unary predicates

We consider the problem of determining the maximum and minimum elements of a setX={x₁...,x _n }, drawn from some finite universeU of real numbers, using only unary predicates of the inputs. It is shown that (n+ log¦U¦) unary predicate evaluations are necessary and sufficient, in the worst case. Results are applied to (i) the problem of determining approximate extrema of a set of real numbers, in the same model, and (ii) the multiparty broadcast communication complexity of determining the extrema of an arbitrary set of numbers held by distinct processors.     

Batch scheduling of step deteriorating jobs

In this paper we consider the problem of scheduling n jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a step function depending on its waiting time, which is the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. For job i, if its waiting time is less than a given threshold value D, then it requires a basic processing time a _i ; otherwise, it requires an extended processing time a _i +b _i . The objective is to minimize the completion time of the last job. We first show that the problem is NP-hard in the strong sense even if all b _i are equal, it is NP-hard even if b _i =a _i for all i, and it is non-approximable in polynomial time with a constant performance guarantee Δ<3/2, unless . We then present O(nlog n) and O(n ^3F−1log n/F ^F ) algorithms for the case where all a _i are equal and for the case where there are F, F≥2, distinct values of a _i , respectively. We further propose an O(n ²log n) approximation algorithm with a performance guarantee for the general problem, where m ^* is the number of batches in an optimal schedule. All the above results apply or can be easily modified for the corresponding open-end bin packing problem.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of (n ²), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/_crit + 1)n(logn)²), wherea b are the lengths of the sides of a rectangle and _crit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.This work was supported partially by the DFG Schwerpunkt Datenstrukturen und Algorithmen, Grants Me 620/6 and Al 253/1, and by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).     

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

Algorithms for projecting points to give the most uniform distribution with applications to hashing

This paper presents several algorithms for projecting points so as to give the most uniform distribution. Givenn points in the plane and an integerb, the problem is to find an optimal angle ofb equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in thetight case in which the two extreme lines are the supporting lines of the point set. The algorithm requiresO(bn² logn) time and On²+bn) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in On²+K log n+bn) time, whereK is the number of intersections in the transformed plane.K is shown to beO(@#@ n²+bn@#@) based on a new counting scheme. The other algorithm is advantageous ifb < n. It performs a simplex range search in each slab to enumerate all the lines that intersectbucket lines, and runs in O(b^0.610n^1.695+K logn) time. It is also shown that the problem can be solved in polynomial time even in therelaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.This work was supported in part by a Grant in Aid for Scientific Research of the Ministry of Education, Science, and Cultures of Japan.     

On a language without star

We solve a problem raised by Boasson [5] concerning the language B^*₁ = s{;xⁿ(y⁺x⁺)^*yⁿ vb; n ? 1s};^*. We prove that t he rational cone generated by B^*₁ which is closed under product but not under the star operation [5] does not contain any non-rational AFL.