Rotation-minimizing osculating frames

An orthonormal frame (_f1,_f2,_f3)$({\mathbf{f}}_1,{\mathbf{f}}_2,{\mathbf{f}}_3)$ is rotation-minimizing   with respect to _fi${\mathbf{f}}_i$ if its angular velocity ω   satisfies ω⋅_fi≡0$\mathit{\omega }\cdot {\mathbf{f}}_i\equiv 0$ — or, equivalently, the derivatives of _fj${\mathbf{f}}_j$ and _fk${\mathbf{f}}_k$ are both parallel to _fi${\mathbf{f}}_i$. The Frenet frame (t,p,b)$(\mathbf{t},\mathbf{p},\mathbf{b})$ along a space curve is rotation-minimizing with respect to the principal normal p, and in recent years adapted frames that are rotation-minimizing with respect to the tangent t have attracted much interest. This study is concerned with rotation-minimizing osculating   frames (f,g,b)$(\mathbf{f},\mathbf{g},\mathbf{b})$ incorporating the binormal b, and osculating-plane vectors f, g that have no rotation about b. These frame vectors may be defined through a rotation of t, p by an angle equal to minus the integral of curvature with respect to arc length. In aeronautical terms, the rotation-minimizing osculating frame (RMOF) specifies yaw-free rigid-body motion along a curved path. For polynomial space curves possessing rational Frenet frames, the existence of rational RMOFs is investigated, and it is found that they must be of degree 7 at least. The RMOF is also employed to construct a novel type of ruled surface, with the property that its tangent planes coincide with the osculating planes of a given space curve, and its rulings exhibit the least possible rate of rotation consistent with this constraint.     

A parameterized view on matroid optimization problems

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n^O(k)$n^{O\left(k\right)}$ time brute force algorithm for finding a k$k$-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅n^O(1)$f\left(k\right)\cdot n^{O\left(1\right)}$) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?$?$, then we can determine in randomized time f(k,?)⋅n^O(1)$f(k,?)\cdot n^{O\left(1\right)}$ whether there is an independent set that is the union of k$k$ blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k$k$-element set in the intersection of ?$?$ matroids, or finding k$k$ terminals in a network such that each of them can be connected simultaneously to the source by ?$?$ disjoint paths.     

OptQC: An optimized parallel quantum compiler

The software package Qcompiler (Chen and Wang 2013) provides a general quantum compilation framework, which maps any given unitary operation into a quantum circuit consisting of a sequential set of elementary quantum gates. In this paper, we present an extended software OptQC  , which finds permutation matrices P$P$ and Q$Q$ for a given unitary matrix U$U$ such that the number of gates in the quantum circuit of U=Q^TP^TU^′PQ$U=Q^T{P}^T{U}^{\prime }PQ$ is significantly reduced, where U^′$U^{\prime }$ is equivalent to U$U$ up to a permutation and the quantum circuit implementation of each matrix component is considered separately. We extend further this software package to make use of high-performance computers with a multiprocessor architecture using MPI. We demonstrate its effectiveness in reducing the total number of quantum gates required for various unitary operators.     

Alternative proof of the Lyndon–Schützenberger Theorem

Some observations on products of primitive words are discussed. By these results, alternative proof is given for the Lyndon–Schützenberger Theorem, which says that every solution of the equation a^mbⁿ=c^k$a^m{b}^n=c^k$ over Σ^*${\Sigma }^{*}$ is trivial.     

Bounding the radii of balls meeting every connected component of semi-algebraic sets

We prove an explicit bound on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set S⊂R^k$S\subset {\mathbb{R}}^k$ defined by a weak sign condition involving s$s$ polynomials in Z[_X1,…,_Xk]$\mathbb{Z}[X_1,\dots ,X_k]$ having degrees at most d$d$, and whose coefficients have bitsizes at most τ$\tau$. Our bound is an explicit function of s,d,k$s,d,k$ and τ$\tau$, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of S$S$ (including the unbounded components). While asymptotic bounds of the form 2^τdO(k)$2^{\tau d^{O\left(k\right)}}$ on these quantities were known before, some applications require bounds which are explicit and which hold for all values of s,d,k$s,d,k$ and τ$\tau$. The bounds proved in this paper are of this nature.     

Non-contractible non-edges in 2-connected graphs

Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible.     

Compatibility of unrooted phylogenetic trees is FPT

A collection of _T1,_T2,…,_Tk$T_1,T_2,\dots ,T_k$ of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree T$T$ such that each tree _Ti$T_i$ can be obtained from T$T$ by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(n^k)$\mathrm{\Omega }(n^k)$ time, n$n$ being the number of leaves. Here, we present an O(nf(k))$\mathrm{O}(\mathit{nf}(k))$ algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number k$k$ of trees.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

Finding the nucleolus of any n-person cooperative game by a single linear program

In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with O(4ⁿ)$O(4^n)$ constraints whose coefficients belong to {−1,0,1}$\{-1,0,1\}$. We discuss the need of having all these constraints and empirically prove that they can be reduced to O(_kmax2ⁿ)$O(k_{\mathit{max}}{2}^n)$, where k_max is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players.     

Computational topology for isotopic surface reconstruction

New computational topology techniques are presented for surface reconstruction of 2-manifolds with boundary, while rigorous proofs have previously been limited to surfaces without boundary. This is done by an intermediate construction of the envelope   (as defined herein) of the original surface. For any compact C²$C^2$-manifold M$M$ embedded in R³${\mathbf{R}}^3$, it is shown that its envelope is C^1,1$C^{1,1}$. Then it is shown that there exists a piecewise linear (PL) subset of the reconstruction of the envelope that is ambient isotopic to M$M$, whenever M$M$ is orientable. The emphasis of this paper is upon the formal mathematical proofs needed for these extensions. (Practical application examples have already been published in a companion paper.) Possible extensions to non-orientable manifolds are also discussed. The mathematical exposition relies heavily on known techniques from differential geometry and topology, but the specific new proofs are intended to be sufficiently specialized to prompt further algorithmic discoveries.     

State-complexity hierarchies of uniform languages of alphabet-size length

We study the state complexity of certain simple languages. If A$A$ is an alphabet of k$k$ letters, then a k$k$-language   is a nonempty set of words of length k$k$, that is, a uniform language of length k$k$. We show that the minimal state complexity of a k$k$-language is k+2$k+2$, and the maximal, (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. We prove constructively that, for every i$i$ between the minimal and maximal bounds, there is a language of state complexity i$i$. We introduce a class of automata accepting sets of words that are permutations of A$A$; these languages define a complete hierarchy of complexities between k²−k+3$k^2-k+3$ and 2^k+1$2^k+1$. The languages of another class of automata, based on k$k$-ary trees, define a complete hierarchy of complexities between 2^k+1$2^k+1$ and (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. This provides new examples of uniform languages of maximal complexity.     

An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes

Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights ω   over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree T^?$T^{?}$ of minimum cost ω(T^?)$\omega (T^{?})$ rooted at r and spanning X.     

On a compact encoding of the swap automaton

Given a string P of length m over an alphabet Σ of size σ, a swapped version of P is a string derived from P   by a series of local swaps, i.e., swaps of adjacent symbols, such that each symbol can participate in at most one swap. We present a theoretical analysis of the nondeterministic finite automaton for the language _?P′∈ΠPΣ^?P^′${?}_{P^{\prime }\in {\Pi }_P}{\Sigma }^{?}{P}^{\prime }$ (swap automaton, for short), where _ΠP${\Pi }_P$ is the set of swapped versions of P  . Our study is based on the bit-parallel simulation of the same automaton due to Fredriksson, and reveals an interesting combinatorial property that links the automaton to the one for the language Σ^?P${\Sigma }^{?}P$. By exploiting this property and the method presented by Cantone et al. (2012), we obtain a bit-parallel encoding of the swap automaton which takes O(σ²⌈k/w⌉)$O({\sigma }^2\lceil k/w\rceil )$ space and allows one to simulate the automaton on a string of length n   in time O(n⌈k/w⌉)$O(n\lceil k/w\rceil )$, where ⌈m/σ⌉?k?m$\lceil m/\sigma \rceil ?k?m$ is the size of a specific factorization of P defined by Cantone et al. (2012) and w is the word size in bits.