Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

The number of roots of a lacunary bivariate polynomial on a line

We prove that a polynomial f∈R[x,y]$f\in \mathbb{R}[x,y]$ with t$t$ non-zero terms, restricted to a real line y=ax+b$y=ax+b$, either has at most 6t−4$6t-4$ zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y−ax−b∈K[x,y]$y-ax-b\in K[x,y]$ divides a lacunary polynomial f∈K[x,y]$f\in K[x,y]$, where K$K$ is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f$f$, in the logarithm of the degree of f$f$, in the degree of the extension K/Q$K/\mathbb{Q}$ and in the logarithmic height of a$a$, b$b$ and f$f$.     

A note on scaling the Linpack benchmark

Dimensional analysis yields a new scaling formula for the Linpack benchmark. The computational power r(_p0,_q0)$r(p_0,q_0)$ on a set of processors decomposed into a (_p0,_q0)$(p_0,q_0)$ grid determines the computational power r(p,q)$r(p,q)$ on a set of processors decomposed into a (p,q)$(p,q)$ grid by the formula r(p,q)=(p/_p0)^α(q/_q0)^βr(_p0,_q0)$r(p,q)=(p/p_0{)}^{\alpha }(q/q_0{)}^{\beta }r(p_0,q_0)$. The two scaling parameters α$\alpha$ and β$\beta$ measure interprocessor communication overhead required by the algorithm. A machine that scales perfectly corresponds to α=β=1$\alpha =\beta =1$; a machine that scales not at all corresponds to α=β=0$\alpha =\beta =0$. We have determined the two scaling parameters by imposing a fixed-time constraint on the problem size such that the execution time remains constant as the number of processors changes. Results for a collection of machines confirm that the formula suggested by dimensional analysis is correct. Machines with the same values for these parameters are self-similar. They scale the same way even though the details of their specific hardware and software may be quite different.     

On some special solutions to periodic Benjamin-Ono equation with discrete Laplacian

We investigate a periodic version of the Benjamin-Ono (BO) equation associated with a discrete Laplacian. We find some special solutions to this equation, and calculate the values of the first two integrals of motion _I1$I_1$ and _I2$I_2$ corresponding to these solutions. It is found that there exists a strong resemblance between them and the spectra for the Macdonald q$q$-difference operators. To better understand the connection between these classical and quantum integrable systems, we consider the special degenerate case corresponding to q=0$q=0$ in more detail. Namely, we give general solutions to this degenerate periodic BO, obtain explicit formulas representing all the integrals of motions _In$I_n$ (n=1,2,…$n=1\text{,}2\text{,}\dots$), and successfully identify it with the eigenvalues of Macdonald operators in the limit q→0$q\to 0$, i.e. the limit where Macdonald polynomials tend to the Hall–Littlewood polynomials.     

Sampling methods for shortest vectors,closest vectors and successive minima

We study four problems from the geometry of numbers, the shortest vector problem  (Svp)$\left(\text{<small-caps>Svp</small-caps>}\right)$, the closest vector problem  (Cvp)$\left(\text{<small-caps>Cvp</small-caps>}\right)$, the successive minima problem  (Smp)$\left(\text{<small-caps>Smp</small-caps>}\right)$, and the shortest independent vectors problem   (Sivp$\text{<small-caps>Sivp</small-caps>}$). Extending and generalizing results of Ajtai, Kumar, and Sivakumar we present probabilistic single exponential time algorithms for all four problems for all _?p${?}_p$ norms. The results on Smp$\text{<small-caps>Smp</small-caps>}$ and Sivp$\text{<small-caps>Sivp</small-caps>}$ are new for all norms. The results on Svp$\text{<small-caps>Svp</small-caps>}$ and Cvp$\text{<small-caps>Cvp</small-caps>}$ generalize previous results of Ajtai et al. for the Euclidean _?2${?}_2$ norm to arbitrary _?p${?}_p$ norms. We achieve our results by introducing a new lattice problem, the generalized shortest vector problem   (GSvp$\text{<small-caps>GSvp</small-caps>}$). ¹ We describe a single exponential time algorithm for GSvp$\text{<small-caps>GSvp</small-caps>}$. We also describe polynomial time reductions from Svp,Cvp,Smp$\text{<small-caps>Svp</small-caps>},\text{<small-caps>Cvp</small-caps>},\text{<small-caps>Smp</small-caps>}$, and Sivp$\text{<small-caps>Sivp</small-caps>}$ to GSvp$\text{<small-caps>GSvp</small-caps>}$, establishing single exponential time algorithms for the four classical lattice problems. This approach leads to a unified algorithmic treatment of the lattice problems Svp,Cvp,Smp$\text{<small-caps>Svp</small-caps>},\text{<small-caps>Cvp</small-caps>},\text{<small-caps>Smp</small-caps>}$, and Sivp$\text{<small-caps>Sivp</small-caps>}$.     

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.     

Optimal number of annuli for maximizing the lifetime of sensor networks

The most effective way to maximize the lifetime of a wireless sensor network (WSN) is to allocate initial energy to sensors such that they exhaust their energy at the same time. The lifetime of a WSN as well as an optimal initial energy allocation are determined by a network design. The main contribution of the paper is to show that the lifetime of a WSN can be maximized by an optimal network design. We represent the network lifetime as a function of the number m$m$ of annuli and show that m$m$ has significant impact on network lifetime. We prove that if the energy consumed by data transmission is proportional to d^α+c$d^{\alpha }+c$, where d$d$ is the distance of data transmission and α$\alpha$ and c$c$ are some constants, then for a circular area of interest with radius R$R$, the optimal number of annuli that maximizes the network lifetime is m=R((α−1)/c)^1/α$m=R{((\alpha -1)/c)}^{1/\alpha }$ for an arbitrary sensor density function.     

Algorithms for near solutions to polynomial equations

Let F(x,y)$F(x,y)$ be a polynomial over a field K$K$ and m$m$ a nonnegative integer. We call a polynomial g$g$ over K$K$ an m$m$-near solution of F(x,y)$F(x,y)$ if there exists a c∈K$c\in K$ such that F(x,g)=cx^m$F(x,g)=c{x}^m$, and the number c$c$ is called an m$m$-value of F(x,y)$F(x,y)$ corresponding to g$g$. In particular, c$c$ can be 0. Hence, by viewing F(x,y)=0$F(x,y)=0$ as a polynomial equation over K[x]$K\left[x\right]$ with variable y$y$, every solution of the equation F(x,y)=0$F(x,y)=0$ in K[x]$K\left[x\right]$ is also an m$m$-near solution. We provide an algorithm that gives all m$m$-near solutions of a given polynomial F(x,y)$F(x,y)$ over K$K$, and this algorithm is polynomial time reducible to solving one variable equations over K$K$. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions.     

Spanners for bounded tree-length graphs

This paper concerns construction of additive stretched spanners with few edges for n$n$-vertex graphs having a tree-decomposition into bags of diameter at most δ$\delta$, i.e., the tree-length δ$\delta$ graphs. For such graphs we construct additive 2δ$2\delta$-spanners with O(δn+nlogn)$O(\delta n+nlogn)$ edges, and additive 4δ$4\delta$-spanners with O(δn)$O\left(\delta n\right)$ edges. This provides new upper bounds for chordal graphs for which δ=1$\delta =1$. We also show a lower bound, and prove that there are graphs of tree-length δ$\delta$ for which every multiplicative δ$\delta$-spanner (and thus every additive (δ−1)$(\delta -1)$-spanner) requires Ω(n^1+1/Θ(δ))$\Omega \left(n^{1+1/\Theta \left(\delta \right)}\right)$ edges.     

Choosing starting values for certain Newton–Raphson iterations

We aim at finding the best possible seed values when computing a^1/p$a^{1/p}$ using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a)$f(a)$ in the interval [_amin,_amax]$[a_{\min },a_{\max }]$, by building the sequence _xn$x_n$ defined by the Newton–Raphson iteration, the natural choice consists in choosing _x0$x_0$ equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between _x0$x_0$ and f(a)$f(a)$. And yet, if we perform n$n$ iterations, what matters is to minimize the maximum possible distance between _xn$x_n$ and f(a)$f(a)$. In several examples, the value of the best starting point varies rather significantly with the number of iterations.     

Modeling and solving the rooted distance-constrained minimum spanning tree problem

In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)$G=(V,E)$ with node set V={0,1,…,n}$V=\{0,1,\dots ,n\}$ and edge set E$E$, two integer weights, a cost _ce$c_e$ and a delay _we$w_e$ associated with each edge e$e$ of E$E$, and a natural (time limit) number H$H$, we wish to find a spanning tree T$T$ of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than H$H$. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.     

Rate-adaptive weighted fair queueing for energy-aware scheduling

In this paper we study energy-aware scheduling that trades energy consumption against a traditional performance measure of delay. We use the power-rate function f(x)=c+x^α$f(x)=c+x^{\alpha }$ for x>0$x>0$ and f(0)=0$f(0)=0$ to model the power consumption, where c>0$c>0$ represents the base power. We give a definition of a rate-adaptive version of the Weighted Fair Queueing scheduling algorithm, and prove its energy consumption is within a bounded factor of the best possible when the algorithm guarantees the classic end-to-end delay for every connection.     

Degree-constrained decompositions of graphs: Bounded treewidth and planarity

We study the problem of decomposing the vertex set V$V$ of a graph into two nonempty parts _V1,_V2$V_1,V_2$ which induce subgraphs where each vertex v∈_V1$v\in V_1$ has degree at least a(v)$a(v)$ inside _V1$V_1$ and each v∈_V2$v\in V_2$ has degree at least b(v)$b(v)$ inside _V2$V_2$. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.     

Approximately optimal trees for group key management with batch updates

We investigate the group key management problem for broadcasting applications. Previous work showed that, in handling key updates, batch rekeying can be more cost effective than individual rekeying. One model for batch rekeying is to assume that every user has probability p$p$ of being replaced by a new user during a batch period with the total number of users unchanged. Under this model, it was recently shown that an optimal key tree can be constructed in linear time when p$p$ is a constant and in O(n⁴)$O\left(n^4\right)$ time when p→0$p\to 0$. In this paper, we investigate more efficient algorithms for the case p→0$p\to 0$, i.e., when membership changes are sparse. We design an O(n)$O\left(n\right)$ heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. Simulation results show that its performance is even better in practice. We also design a refined heuristic algorithm and show that it achieves an approximation ratio of 1+?$1+?$ for any fixed ?>0$?>0$ and n$n$, as p→0$p\to 0$. Finally, we give another approximation algorithm for any p∈(0,0.693)$p\in (0,0.693)$ which is shown to be quite good by our simulations.