Stability of polynomials under coefficient perturbation

Let the real polynomiala_{0}x^{n} + a_{1}x^{n-1} + ... + a_{n-1}x + a_{n}be stable and let the real numbersb_{k}, c_{k} geq 0, 0 leq k leq n, be given. We present a simple determinant criterion for finding the largestt_{0} geq 0such that the polynomialalpha_{0}x^{n} + alpha_{1}x^{n-1}+ ... +alpha_{n-1}x + alpha_{n}is stable for allalpha_{k} in (a_{k} - b_{k}t_{0}, a_{k} + C_{k}t_{0}) cup {a_{k}}, 0 leq k leq n. Several further observations allow us to reduce the computational cost considerably.     

B样条曲线同时插入多个节点的快速算法

基于离散B样条的一个新的递推公式，提出B样条曲线同时插入多个节点的新算法。不同于Cohen等插入节点的Oslo算法，本算法用新的方法离算离散B样条，求每个离散B样条的值只需O(1)的运算量，从而使本算法高效，其时间复杂性为O(sk n)，其中k为B样条曲线的阶，n k 1为原节点数，s为新插入节点的个数,本算法的通用性强，适用于端点插值的和非端点插值的B样条曲线，可同时在曲线定义域内外的任意位置上插入任意个节点。     

Efficient Algorithms for k Maximum Sums

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem involves finding the k largest values of for The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a -time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in time in the worst case. Our algorithm is optimal for and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.     

Convergence to Suitable Weak Solutions for a Finite Element Approximation of the Navier–Stokes Equations with Numerical Subgrid Scale Modeling

In this article, a Galerkin finite element approximation for a class of time–space fractional differential equation is studied, under the assumption that \(u_{tt}, u_{ttt}, u_{2\alpha ,tt}\) are continuous for \(\varOmega \times (0,T]\), but discontinuous at time \(t=0\). In spatial direction, the Galerkin finite element method is presented. And in time direction, a Crank–Nicolson time-stepping is used to approximate the fractional differential term, and the product trapezoidal method is employed to treat the temporal fractional integral term. By using the properties of the fractional Ritz projection and the fractional Ritz–Volterra projection, the convergence analyses of semi-discretization scheme and full discretization scheme are derived separately. Due to the lack of smoothness of the exact solution, the numerical accuracy does not achieve second order convergence in time, which is \(O(k^{3-\beta }+k^{3}t_{n+1}^{-\beta }+k^{3}t_{n+1}^{-\beta -1})\), \(n=0,1,\ldots ,N-1\). But the convergence order in time is shown to be greater than one. Numerical examples are also included to demonstrate the effectiveness of the proposed method.     

Inversion Of A Generalized Vandermonde Matrix

In this paper the author gives an explicit closed form expression for the $n\times n$ inverse matrix $(V_{G}^{(k)})^{-1}(n)$ of the $n\times n$ Vandermonde matrix $V_{G}^{(k)}(n)$ by using the elementary symmetric functions. Symbolic and numerical results are presented.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

Lower Bounds for Agnostic Learning via Approximate Rank

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose that there exist functions f₁, ?, f_r\phi_{1}, \ldots , \phi_{r} : {− 1, 1}ⁿ → \mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3 for some reals a₁, ?, a_r\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq exp \{\Omega(\sqrt{n})\}$r \geq exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority functions, we obtain a lower bound of W(2ⁿ/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2ⁿ for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi (1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

Finding Pathway Structures in Protein Interaction Networks

The increased availability of data describing biological interactions provides important clues on how complex chains of genes and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find an optimal path structure in time and space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure. Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures, we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity by applying it to protein interaction networks in the DIP database.     

On the span reachability of polynomial state-affine systems

The purpose of this report is to derive an explicit condition for the span reachability of a discrete polynomial state-affine system described byx(k+1)=(A_{0} +Sigmamin{i=1}max{r}u^{i}(k)A_{i})x(k)+ summin{i=1}max{r} u^{i}(k)B_{i}, (k=0,1,...)(1) whereris a positive integer,x in R^{n}, u in R^{1},u^{i}denotes the ith power ofu, and Aiand Biare matrices of appropriate dimensions. In order to define input sequences which can construct reachable state vectors from the origin to span the whole state space, a generalized type of the Vandermonde's matrix is newly defined and utilized fully. Although the algebraic structure of (1) is more complicated than discrete bilinear systems, the result turns out to be quite analogous to each other.     

A Combinatorial Analysis for the Critical Clause Tree

In Paturi, Pudlák, Saks, and Zane (Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS1998), pp. 628–637, 1998) proposed a simple randomized algorithm for finding a satisfying assignment of a k-CNF formula. The main lemma of the paper is as follows: Given a satisfiable k-CNF formula that has a d-isolated satisfying assignment z, the randomized algorithm finds z with probability at least $2^{-(1-\mu_{k}/(k-1)+\epsilon_{k}(d))n}$ , where $\mu_{k}/(k-1)=\sum_{i=1}^{\infty}1/(i((k-1)i+1))$ , and ? _k (d)=o _d (1). They estimated the lower bound of the probability in an analytical way, and used some asymptotics. In this paper, we analyze the same randomized algorithm, and estimate the probability in a combinatorial way. The lower bound we obtain is a little simpler: $2^{-(1-\mu_{k}(d)/(k-1))n}$ , where $\mu_{k}(d)/(k-1)=\sum_{i=1}^{d}1/(i((k-1)i+1))$ . This value is a little bit larger (i.e., better) than that of Paturi et al. (Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS1998), pp. 628–637, 1998) although the two values are asymptotically equal when d=ω(1).     

The <Emphasis Type="Italic">k</Emphasis>-Homotopic Thinning and a Torus-Like Digital Image in <Emphasis Type="Bold">Z</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In order to discuss digital topological properties of a digital image (X,k), many recent papers have used the digital fundamental group and several digital topological invariants such as the k-linking number, the k-topological number, and so forth. Owing to some difficulties of an establishment of the multiplicative property of the digital fundamental group, a k-homotopic thinning method can be essentially used in calculating the digital fundamental group of a digital product with k-adjacency. More precisely, let be a simple closed k _i -curve with l _i elements in . For some k-adjacency of the digital product which is a torus-like set, proceeding with the k-homotopic thinning of , we obtain its k-homotopic thinning set denoted by DT _k . Writing an algorithm for calculating the digital fundamental group of , we investigate the k-fundamental group of by the use of various properties of a digital covering (Z×Z,p ₁×p ₂,DT _k ), a strong k-deformation retract, and algebraic topological tools. Finally, we find the pseudo-multiplicative property (contrary to the multiplicative property) of the digital fundamental group. This property can be used in classifying digital images from the view points of both digital k-homotopy theory and mathematical morphology.

TSP Heuristics: Domination Analysis and Complexity

We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph Kn produce a solution no worse than the average cost of a tour in Kn in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon, Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than $\lceil{n}/{2}\rceil !$ , and for the Double Tree heuristic and a variation of the Christofides heuristic the domination numbers are shown to be one (even if the edge costs satisfy the triangle inequality). Further, unless P = NP, no polynomial time approximation algorithm exists for the TSP on the complete digraph $\vec{K}_n$ with domination number at least (n-1)!-k for any constant k or with domination number at least (n-1)! - (( k /(k+1))(n+r))!-1 for any non-negative constants r and k such that (n+r) $\equiv$ 0 mod (k+1). The complexities of finding the median value of costs of all the tours in $\vec{K}_n$ and of similar problems are also studied.     

Componentwise asymptotic stability of linear constant dynamical systems

This note deals with a special type of asymptotic stability, namely componentwise asymptotic stability with respect to the vectorgamma(t)(CWASγ) of systemS: dot{x} = Ax + Bu, t geq 0, wheregamma(t) > 0(componentwise inequality) andgamma(t) rightarrow 0ast rightarrow + infty.Sis CWASγ if for eacht_{0} geq 0and for each|x(t_{0})| leq gamma (t_{0}) (|x (t_{0})|with the components|x_{i}(t_{0})|the free response ofSsatisfies|x(t)| leq gamma (t)for eacht geq t_{0}. Forgamma(t){underline { underline delta} } alphae^{-beta t}, t geq 0, withalpha > 0andbeta > 0(scalar), the CWEAS (E= exponential) may be defined.Sis CWAS γ (CWEAS) if and only ifdot{gamma}(t) geq bar{A}gamma(t), t geq 0 (bar{A}alpha < 0); A {underline { underline delta} } (a_{ij})andbar{A}has the elements aijand|a_{ij}|, i neq j. These results may be used in order to evaluate in a more detailed manner the dynamical behavior ofSas well as to stabilizeScomponentwise by a suitable linear state feedback.     

Matching Polyhedral Terrains Using Overlays of Envelopes

For a collection $\F$ of $d$-variate piecewise linear functions of overall combinatorial complexity $n$, the lower envelope $\E(\F)$ of $\F$ is the pointwise minimum of these functions. The minimization diagram $\M(\F)$ is the subdivision of $\reals^d$ obtained by vertically (i.e., in direction $x_{d+1}$) projecting $\E(\F)$. The overlay $\O(\F,\G)$ of two such subdivisions $\M(\F)$ and $\M(\G)$ is their superposition. We extend and improve the analysis of de Berg et al. \cite{bgh-vdt3s-96} by showing that the combinatorial complexity of $\O(\F,\G)$ is $\Omega(n^d \alpha^{2}(n))$ and $O(n^{d+\eps})$ for any $\eps>0$ when $d \ge 2$, and $O(n^2 \alpha(n) \log n)$ when $d=2$. We also describe an algorithm that constructs $\O(\F,\G)$ in this time. We apply these results to obtain efficient general solutions to the problem of matching two polyhedral terrains in higher dimensions under translation. That is, given two piecewise linear terrains of combinatorial complexity $n$ in $\reals^{d+1}$, we wish to find a translation of the first terrain that minimizes its distance to the second, according to some distance measure. For the perpendicular distance measure, which we adopt from functional analysis since it is natural for measuring the similarity of terrains, we present a matching algorithm that runs in time $O(n^{2d+\eps})$ for any $\eps>0$. Sharper running time bounds are shown for $d \le 2$. For the directed and undirected \Hd\ distance measures, we present a matching algorithm that runs in time $O(n^{d^2+d+\eps})$ for any $\eps>0$.     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

Real-time scheduling with resource sharing on heterogeneous multiprocessors

Consider the problem of scheduling a task set τ of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has m _k processors of type-k, where k∈{1,2,…,t}. The execution time of a task depends on the type of processor on which it executes. The set of shared resources is denoted by R. For each task τ _i , there is a resource set R _i ?R such that for each job of τ _i , during one phase of its execution, the job requests to hold the resource set R _i exclusively with the interpretation that (i) the job makes a single request to hold all the resources in the resource set R _i and (ii) at all times, when a job of τ _i holds R _i , no other job holds any resource in R _i . Each job of task τ _i may request the resource set R _i at most once during its execution. A job is allowed to migrate when it requests a resource set and when it releases the resource set but a job is not allowed to migrate at other times. Our goal is to design a scheduling algorithm for this problem and prove its performance. We propose an algorithm, LP-EE-vpr, which offers the guarantee that if an implicit-deadline sporadic task set is schedulable on a t-type heterogeneous multiprocessor platform by an optimal scheduling algorithm that allows a job to migrate only when it requests or releases a resource set, then our algorithm also meets the deadlines with the same restriction on job migration, if given processors $4 \times (1 + \operatorname{MAXP}\times \lceil \frac{\vert P\vert \times\operatorname{MAXP}}{\min \{m_{1}, m_{2}, \ldots, m_{t} \}} \rceil )$ times as fast. (Here $\operatorname{MAXP}$ and |P| are computed based on the resource sets that tasks request.) For the special case that each task requests at most one resource, the bound of LP-EE-vpr collapses to $4 \times (1 + \lceil \frac{\vert R\vert }{\min \{m_{1}, m_{2}, \ldots, m_{t} \}} \rceil )$ . To the best of our knowledge, LP-EE-vpr is the first algorithm with proven performance guarantee for real-time scheduling of sporadic tasks with resource sharing on t-type heterogeneous multiprocessors.