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.     

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.     

Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints

In this paper we consider the problem of scheduling n$n$ preemptive jobs on m$m$ machines with identical speed under machine availability and eligibility constraints when minimizing maximum lateness (_Lmax$(L_{\max }$). The lateness of a job is defined to be its completion time minus its due date, and _Lmax$L_{\max }$ is the maximum value of lateness among all jobs. We assume that each machine is not continuously available at all time throughout the planning horizon and each job is only allowed to be processed on specific machines. Network flow technique is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time two-phase binary search algorithm to verify the feasibility of the problem and to solve the scheduling problem optimally if a feasible schedule exists. Finally, we show that the time complexity of the algorithm is O((n+(2n+2x))³log(UB-LB))$O((n+(2n+2x){)}^3\log (\text{<italic>UB</italic>}-\text{<italic>LB</italic>}))$. Most literature in parallel machine scheduling assume that all machines are continuously available for processing and all jobs can be processed at any available machine throughout the planning horizon. But both assumptions might not be true in some practical environment, such as machine preventive maintenance and machines that have different capabilities to process jobs. This type of scheduling problem is seldom studied in the literature. The purpose of this paper is to examine the scheduling problem with machines with identical speed under machine availability and eligibility constraints. The objective is to minimize maximum lateness. We formulate this scheduling problem into a series of maximum flow problems with different values of _Lmax$L_{\max }$. A polynomial time two-phase binary search algorithm is proposed to verify the feasibility of the problem and to determine the optimal _Lmax$L_{\max }$.     

Asynchronous deterministic rendezvous in graphs

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D   in an infinite line, we show a rendezvous algorithm with cost O(D|_Lmin|²)$\mathrm{O}(D|L_{\min }{|}^2)$ when D   is known and O((D+|_Lmax|)³)$\mathrm{O}((D+\left|L_{\max }\right|{)}^3)$ if D   is unknown, where |_Lmin|$\left|L_{\min }\right|$ and |_Lmax|$\left|L_{\max }\right|$ are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O(n|_Lmin|)$\mathrm{O}(n|L_{\min }|)$, if the size n   of the ring is known, and of cost O(n|_Lmax|)$\mathrm{O}(n|L_{\max }|)$, if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O(D|_Lmin|)$\mathrm{O}(D|L_{\min }|)$ if the topology of the graph and the initial positions are known to agents.     

Hypothesis testing in rank-size rule regression

This note examines testing methods for Paretoness in the framework of rank-size rule regression. Rank-size rule regression describes a relationship found in the analysis of various topics such as city population, words in texts, scale of companies and so on. In terms of city population, it is basically an empirical rule that log?(_S(i))$\log ?(S_{(i)})$ is approximately a linear function of log?(i)$\log ?(i)$ where _S(i)$S_{(i)}$ is the number of population of i  th largest city in a country. This is closely related to the so-called Zipf’s law. It is known that this kind of empirical observation is found when the city population is a random variable following a Pareto distribution. Thus one may be willing to test if city size has a Pareto distribution or not. Rosen and Resnick [K.T. Rosen, M. Resnick, The size distribution of cities: an explanation of the Pareto law and primacy, Journal of Urban Economics 8 (1980), 165–186] and Soo [K.T. Soo, Zipf’s law for cities: a cross country investigation, Regional Science and Urban Economics (35) 2005, 239–263] regress log?(_S(i))$\log ?(S_{(i)})$ on log?(i)$\log ?(i)$ and log?²(i)${\log ?}^2(i)$ and test the null of Paretoness by standard t-test for the latter regressor. It is found that t-statistics take large values and the Paretoness is rejected in many countries. We study the statistical properties of the t-statistic and show that it explodes asymptotically, in fact, by simulation and thus the t-test does not provide a reasonable testing procedure. We propose an alternative test statistic which seems to be asymptotically normally distributed. We also propose a test with the null hypothesis that the city size distribution is Pareto with exponent unity, which is a modification of the F-test.     

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

Computing phylogenetic roots with bounded degrees and errors is NP-complete

In this paper we study the computational complexity of the following optimization problem: given a graph G=(V,E)$G=(V,E)$, we wish to find a tree T such that (1) the degree of each internal node of T   is at least 3 and at most Δ$\Delta$, (2) the leaves of T are exactly the elements of V, and (3) the number of errors, that is, the symmetric difference between E   and {{u,v}:u,v$\{\{u,v\}:u,v$ are leaves of T   and _dT(u,v)≤k}$d_T(u,v)\le k\}$, is as small as possible, where _dT(u,v)$d_T(u,v)$ denotes the distance between u$u$ and v$v$ in tree T  . We show that this problem is NP-hard for all fixed constants Δ,k≥3$\Delta ,k\ge 3$.     

Graphs of interval count two with a given partition

We describe a polynomial time algorithm to decide for a given connected graph G and a given partition of its vertex set into two sets A and B  , whether it is possible to assign a closed interval I(u)$I(u)$ to each vertex u of G such that two distinct vertices u and v of G   are adjacent if and only if I(u)$I(u)$ and I(v)$I(v)$ intersect, all intervals assigned to vertices in A   have some length _LA$L_A$, and all intervals assigned to vertices in B   have some length _LB$L_B$ where _LA<_LB$L_A<L_B$. Our result is motivated by the interval count problem whose complexity status is open.     

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.     

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 mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)$G=(V,E)$ with a set of terminals K⊂V$K\subset V$, a mimicking network   is a smaller graph H=(_VH,_EH)$H=(V_H,E_H)$ which contains the set of terminals K   and for every bipartition [U,K−U]$[U,K-U]$ of the terminals, the cost of the minimum cut separating U   from K−U$K-U$ in G is exactly equal to the cost of the minimum cut separating U   from K−U$K-U$ in H.     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

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.     

A memetic algorithm for the job-shop with time-lags

The job-shop with time-lags (JS|t)$(\text{<italic>JS</italic>}|t)$ is defined as a job-shop problem with minimal and maximal delays between starting times of operations. In this article, time-lags between successive operations of the same job (JS|_ti,si)$(\text{<italic>JS</italic>}|t_{i,s_i})$ are studied. This problem is a generalization of the job-shop problem (null minimal time-lags and infinite maximal time-lags) and the no-wait job-shop problem (null minimal and maximal time-lags). This article introduced a framework based on a disjunctive graph to modelize the problem and on a memetic algorithm for job sequence generation on machines.     

A comparison of CPU and GPU implementations for solving the Convection Diffusion equation using the local Modified SOR method

In this paper we study a parallel form of the SOR method for the numerical solution of the Convection Diffusion equation suitable for GPUs using CUDA. To exploit the parallelism offered by GPUs we consider the fine grain parallelism model. This is achieved by considering the local relaxation version of SOR. More specifically, we use SOR with red-black ordering using two sets of parameters _ω1ij${\omega }_{1\mathit{ij}}$ and _ω2ij${\omega }_{2\mathit{ij}}$ for the 5 point stencil. The parameter _ω1ij${\omega }_{1\mathit{ij}}$ is associated with each red (i + j   even) grid point (i,j)$(i\text{,}j)$, whereas the parameter _ω2ij${\omega }_{2\mathit{ij}}$ is associated with each black (i+j$(i+j$ odd) grid point (i,j)$(i\text{,}j)$. The use of a parameter for each grid point avoids the global communication required in the adaptive determination of the best value of ω$\omega$ and also increases the convergence rate of the SOR method (Varga, 1962) [38] and (Young, 1971) [41]. We present our strategy and the results of our effort to exploit the computational capabilities of GPUs under the CUDA environment. Additionally, two parallel CPU programs utilizing manual SSE2 (Streaming SIMD Extensions 2) and AVX (Advanced Vector Extensions) vectorization were developed as performance references. The optimizations applied on the GPU version were also considered for the CPU version. Significant performance improvement was achieved with all three developed GPU kernels differentiated by the degree of recomputations thus affecting the flops per element access ratio.