Local edge colouring of Yao-like subgraphs of Unit Disk Graphs

The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like   subgraphs of Unit Disk Graphs. These are geometric graphs such that for some positive integers l,k$l,k$ the following property holds at each node v$v$: if we partition the unit circle centered at v$v$ into 2k$2k$ equally sized wedges then each wedge can contain at most l$l$ points different from v$v$. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k$k$ and l$l$, but not on the size of the graph) number of hops (measured in the original underlying Unit Disk Graph) away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl+1$2kl+1$ and this is optimal for local algorithms (since the maximal degree is 2kl$2kl$ and a colouring with 2kl$2kl$ colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.     

Quadratic programming with transaction costs

We consider the problem of maximizing the mean-variance utility function of n$n$ assets. Associated with a change in an asset's holdings from its current or target value is a transaction cost. These must be accounted for in practical problems. A straightforward way of doing so results in a 3n$3n$-dimensional optimization problem with 3n$3n$ additional constraints. This higher dimensional problem is computationally expensive to solve. We present an algorithm for solving the 3n$3n$-dimensional problem by modifying an active set quadratic programming (QP) algorithm to solve the 3n$3n$-dimensional problem as an n$n$-dimensional problem accounting for the transaction costs implicitly rather than explicitly. The method is based on deriving the optimality conditions for the higher dimensional problem solely in terms of lower dimensional quantities and requires substantially less computational effort than any active set QP algorithm applied directly on a 3n$3n$-dimensional problem.     

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

On semimeasures predicting Martin-Löf random sequences

Solomonoff’s central result on induction is that the prediction of a universal semimeasure M$M$ converges rapidly and with probability 1 to the true sequence generating predictor μ$\mu$, if the latter is computable. Hence, M$M$ is eligible as a universal sequence predictor in the case of unknown μ$\mu$. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M$M$ itself. We show that there are universal semimeasures M$M$ which do not converge to μ$\mu$ on all μ$\mu$-random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D$D$ as a mixture over all computable measures and the enumerable semimeasure W$W$ as a mixture over all enumerable nearly measures. We show that W$W$ converges to D$D$ and D$D$ to μ$\mu$ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.     

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.     

Rational two-parameter families of spheres and rational offset surfaces

The present paper investigates two-parameter families of spheres in R³${\mathbb{R}}^3$ and their corresponding two-dimensional surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$. Considering a rational surface Φ$\Phi$ in R⁴${\mathbb{R}}^4$, the envelope surface Ψ$\Psi$ of the corresponding family of spheres in R³${\mathbb{R}}^3$ is typically non-rational. Using a classical sphere-geometric approach, we prove that the envelope surface Ψ$\Psi$ and its offset surfaces admit rational parameterizations if and only if Φ$\Phi$ is a rational sub-variety of a rational isotropic hyper-surface in R⁴${\mathbb{R}}^4$. The close relation between the envelope surfaces Ψ$\Psi$ and rational offset surfaces in R³${\mathbb{R}}^3$ is elaborated in detail. This connection leads to explicit rational parameterizations for all rational surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$ whose corresponding two-parameter families of spheres possess envelope surfaces admitting rational parameterizations. Finally we discuss several classes of surfaces sharing this property.     

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.     

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.     

Algorithms for a class of infinite permutation groups

Motivated by the famous 3n+1$3n+1$ conjecture, we call a mapping from Z$\mathbb{Z}$ to Z$\mathbb{Z}$residue-class-wise affine   if there is a positive integer m$m$ such that it is affine on residue classes (mod m$m$). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings.     

Transposition invariant words

We define an operation called transposition on words of fixed length. This operation arises naturally when the letters of a word are considered as entries of a matrix. Words that are invariant with respect to transposition are of special interest. It turns out that transposition invariant words have a simple interpretation by means of elementary group theory. This leads us to investigate some properties of the ring of integers modulo n$n$ and primitive roots. In particular, we show that there are infinitely many prime numbers p$p$ with a primitive root dividing p+1$p+1$ and infinitely many prime numbers p$p$ without a primitive root dividing p+1$p+1$. We also consider the orbit of a word under transposition.     

Paths and trails in edge-colored graphs

This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s$s$ and t$t$ in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t$s-t$ path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s$s$ and t$t$ for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k$k$ pairwise vertex/edge disjoint properly edge-colored s−t$s-t$ paths/trails in a c$c$-edge-colored graph G^c$G^c$ is NP-complete even for k=2$k=2$ and c=Ω(n²)$c=\Omega \left(n^2\right)$, where n$n$ denotes the number of vertices in G^c$G^c$. Moreover, we prove that these problems remain NP-complete for c$c$-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n)$c=\Omega \left(n\right)$. We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.     

Static load-balanced routing for slimmed fat-trees

Slimmed fat-trees have recently been proposed and deployed to reduce costs in High Performance Computing (HPC) clusters. While existing static routing schemes such as destination-mod-k (D-mod-k) routing are load-balanced and effective for full bisection bandwidth fat-trees, they incur significant load imbalance in many slimmed fat-trees. In this work, we propose a static load balanced routing scheme, called Round-Robin Routing (RRR$RRR$), for 2$2$- and 3$3$-level extended generalized fat-trees (XGFTs), which represent many fat-tree variations including slimmed fat-trees. RRR$RRR$ achieves near perfect load-balancing for any such XGFT in that links at the same level of a tree carry traffic from almost the same number of source–destination pairs. Our evaluation results indicate that on many slimmed fat-trees, RRR$RRR$ is significantly better than D-mod-k for dense traffic patterns due to its better load-balancing property, but performs worse for sparse patterns. We develop a combined routing scheme that enjoys the strengths of both RRR$RRR$ and D-mod-k by using RRR$RRR$ in conjunction with D-mod-k. The combined routing is a robust load-balanced routing scheme for slimmed fat-trees: it performs similar to D-mod-k for sparse traffic patterns and to RRR$RRR$ for dense patterns.     

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.     

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.     

Bounds on the bisection width for random d -regular graphs

In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the bisection width of random d$d$-regular graphs, for any value of d$d$. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of d$d$-regular graphs. We provide bounds for 5≤d≤12$5\le d\le 12$. We also give empirical values of the size of the bisection found by the algorithm for some small values of d$d$ and compare them with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum bisection.     

Expanders and time-restricted branching programs

The replication number   of a branching program is the minimum number R$R$ such that along every accepting computation at most R$R$ variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0$0$ (read-once programs) and the total number n$n$ of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn)$R=o(n/logn)$. We improve this to R≤?n$R\le ?n$ for a constant ?>0$?>0$. This also gives an alternative and simpler proof of an exponential lower bound for (1+?)n$(1+?)n$ time branching programs for a constant ?>0$?>0$. We prove these lower bounds for quadratic functions of Ramanujan graphs.