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.     

On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

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.     

Adaptive timeliness of consensus in presence of crash and timing faults

The Δ$\mathrm{\Delta }$-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ$\mathrm{\Delta }$ (Δ$\mathrm{\Delta }$-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ$\mathrm{\Delta }$-timed uniform consensus problem in presence of _fc$f_{\mathrm{c}}$ crash processes and _ft$f_{\mathrm{t}}$ timing-faulty processes, and propose a Δ$\mathrm{\Delta }$-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ$\mathrm{\Delta }$-timed uniform consensus when at least _ft+1$f_{\mathrm{t}}+1$ correct processes exist in the system. If the system has less than _ft+1$f_{\mathrm{t}}+1$ correct processes, the algorithm cannot solve the Δ$\mathrm{\Delta }$-timed uniform consensus. However, as long as _ft+1$f_{\mathrm{t}}+1$ processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes requires that the system has at least _ft+1$f_{\mathrm{t}}+1$ correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than _ft+1$f_{\mathrm{t}}+1$ non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

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

Complexity of question/answer games

Question/Answer games (Q/A games for short) are a generalization of the Rényi–Ulam game and they are a model for information extraction in parallel. A Q/A game, G=(D,s,(_q1,…,_qk))$G=(D,s,(q_1,\dots ,q_k))$, is played on a directed acyclic graph, D=(V,E)$D=(V,E)$, with a distinguished start vertex s$s$. In the i$i$th round, Paul selects a set, _Qi⊆V$Q_i\subseteq V$, of at most _qi$q_i$ non-terminal vertices. Carole responds by choosing an outgoing edge from each vertex in _Qi$Q_i$. At the end of k$k$ rounds, Paul wins if Carole’s answers define a unique path from the root to one of the terminal vertices in D$D$.     

A palindromization map for the free group

We define a self-map Pal:_F2→_F2$Pal:F_2\to F_2$ of the free group on two generators a,b$a,b$, using automorphisms of _F2$F_2$ that form a group isomorphic to the braid group _B3$B_3$. The map Pal$Pal$ restricts to de Luca’s right iterated palindromic closure on the submonoid generated by a,b$a,b$. We show that Pal$Pal$ is continuous for the profinite topology on _F2$F_2$; it is the unique continuous extension of de Luca’s right iterated palindromic closure to _F2$F_2$. The values of Pal$Pal$ are palindromes and coincide with the elements g∈_F2$g\in F_2$ such that abg$abg$ and bag$bag$ are conjugate.     

Minimum cost source location problem with local 3-vertex-connectivity requirements

Let G=(V,E)$G=(V,E)$ be a simple undirected graph with a set V$V$ of vertices and a set E$E$ of edges. Each vertex v∈V$v\in V$ has a demand d(v)∈_Z+$d\left(v\right)\in Z_{+}$ and a cost c(v)∈_R+$c\left(v\right)\in R_{+}$, where _Z+$Z_{+}$ and _R+$R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G$G$ requires finding a set S$S$ of vertices minimizing _∑v∈Sc(v)${\sum }_{v\in S}c\left(v\right)$ such that there are at least d(v)$d\left(v\right)$ pairwise vertex-disjoint paths from S$S$ to v$v$ for each vertex v∈V−S$v\in V-S$. It is known that if there exists a vertex v∈V$v\in V$ with d(v)≥4$d\left(v\right)\ge 4$, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(|V|⁴log²|V|)$O\left({\left|V\right|}^4{log}^2\left|V\right|\right)$ time if d(v)≤3$d\left(v\right)\le 3$ holds for each vertex v∈V$v\in V$.     

An efficient method of DFT/LDA band-gap correction

It has been shown that the underestimated by DFT/LDA(GGA) band-gap can be efficiently corrected by an averaging procedure of transition energies over a region close to the direct band-gap transition, which we call the Δ(EIG)$\Delta \left(EIG\right)$ method (the differences in the Kohn–Sham eigenvalues). For small excitations the averaging appears to be equivalent to the Δ(SCF)$\Delta \left(SCF\right)$ approach (differences in the self-consistent energies), which is a consequence of Janak’s theorem and has been confirmed numerically. The Gaussian distribution in k$k$-space for electronic excitation has been used (occupation numbers in the Δ(SCF)$\Delta \left(SCF\right)$ or eigenenergy sampling in the Δ(EIG)$\Delta \left(EIG\right)$). A systematic behavior of the k$k$-space localization parameter _σk${\sigma }_k$ correcting the band-gap has been observed in numerical experiments. On that basis some sampling schemes for band-gap correction have been proposed and tested in the prediction of the band-gap behavior in I_nxG_a(1−x)N$I{n}_{x}G{a}_{(1-x)}N$ semiconducting alloy, and a very good agreement with independent calculations has been obtained. In the context of the work the issue of electron localization in the r$r$-space has been discussed which, as it has been predicted by Mori-Sánchez et al. [P. Mori-Sánchez, A.J. Cohen, W. Yang, Phys. Rev. Lett. 100 (2008) 146401], should reduce the effect of the convex behavior of the LDA/GGA functionals and improve the band-gap prediction within DFT/LDA(GGA). A scheme for electron localization in r$r$-space has been suggested.     

Drawing slicing graphs with face areas

We consider orthogonal drawings of a plane graph G$G$ with specified face areas. For a natural number k$k$, a k$k$-gonal drawing of G$G$ is an orthogonal drawing such that the boundary of G$G$ is drawn as a rectangle and each inner face is drawn as a polygon with at most k$k$ corners whose area is equal to the specified value. In this paper, we show that every slicing graph G$G$ with a slicing tree T$T$ and a set of specified face areas admits a 10-gonal drawing D$D$ such that the boundary of each slicing subgraph that appears in T$T$ is also drawn as a polygon with at most 10 corners. Such a drawing D$D$ can be found in linear time.     

Pareto and scalar bicriterion optimization in scheduling deteriorating jobs

In the paper two problems of a single machine bicriterion scheduling of a set of deteriorating jobs are considered. The jobs are independent, nonpreemptable and are ready for processing at time 0$0$. The processing time _pj$p_j$ of each job is a linear function of the starting time _Sj$S_j$ of the job, _pj=1+_αjSj$p_j=1+{\alpha }_j{S}_j$, where _Sj?0$S_j?0$ and _αj>0${\alpha }_j>0$ for j=0,1,...,n$j=0,1,...,n$.     

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.     

Borderedness-preserving homomorphisms

This paper aims at investigating properties of homomorphisms which preserve the bordered words. The bordered words are classified into _d1$d_1$-words and _d2$d_2$-words, where the length of the proper border of _d2$d_2$-word is greater than half of it. Some characterizations of _d1$d_1$-word-preserving homomorphism are studied. Some relationships among d-primitivity-preserving homomorphisms, _d1$d_1$-word-preserving homomorphisms, and _d2$d_2$-word-preserving homomorphisms are investigated. We show that every d-primitivity-preserving homomorphism is _d1$d_1$-word-preserving and every _d1$d_1$-word-preserving homomorphism is _d2$d_2$-word-preserving.