Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³)$\mathrm{O}(n^2{m}^3)$, where the size of the text is n×n$n\times n$ and the size of the pattern is m×m$m\times m$. In this paper we present a new algorithm for the problem whose running time is O(n²m²)$\mathrm{O}(n^2{m}^2)$.     

Approximating the traffic grooming problem in tree and star networks

We consider the problem of grooming paths in all-optical networks with tree topology so as to minimize the switching cost, measured by the total number of used ADMs. We first present efficient approximation algorithms with approximation factor of 2ln(δ⋅g)+o(ln(δ⋅g))$2ln(\delta \cdot g)+o(ln(\delta \cdot g))$ for any fixed node degree bound δ$\delta$ and grooming factor g$g$, and 2lng+o(lng)$2lng+o(lng)$ in unbounded degree directed trees, respectively. In the attempt to extend our results to general undirected trees, we completely characterize the complexity of the problem in star networks by providing polynomial time optimal algorithms for g≤2$g\le 2$ and proving the intractability of the problem for any fixed g>2$g>2$. While for general topologies, the problem was known to be NP-hard g$g$ not constant, the complexity for fixed values of g$g$ was still an open question.     

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.     

An efficient construction of one-to-many node-disjoint paths in folded hypercubes

A folded hypercube is basically a hypercube with additional links augmented, where the additional links connect all pairs of nodes with longest distance in the hypercube. In an n$n$-dimensional folded hypercube, it has been shown that n+1$n+1$ node-disjoint paths from one source node to other n+1$n+1$ (mutually) distinct destination nodes, respectively, can be constructed in O(n⁴)$O\left(n^4\right)$ time so that their maximal length is not greater than ⌈n/2⌉+1$\lceil n/2\rceil +1$, where n+1$n+1$ is the connectivity and ⌈n/2⌉$\lceil n/2\rceil$ is the diameter. Besides, their maximal length is minimized in the worst case. In this paper, we further show that by minimizing the computations of minimal routing functions, these node-disjoint paths can be constructed in O(n³)$O\left(n^3\right)$ time, which is more efficient, and is hard to be reduced because it must take O(n³)$O\left(n^3\right)$ time to compute a minimal routing function by solving a corresponding maximum weighted bipartite matching problem with the best known algorithm.     

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.     

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.     

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.     

Approximation algorithms for orthogonal packing problems for hypercubes

Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many different settings. The input consists of a set I={_r1,…,_rn}$I=\{r_1,\dots ,r_n\}$ of d$d$-dimensional rectangular items _ri=(_ai,1,…,_ai,d)$r_i=(a_{i,1},\dots ,a_{i,d})$ and a space Q$Q$. The task is to pack the items in an orthogonal and non-overlapping manner without using rotations into the given space. In the strip packing setting the space Q$Q$ is given by a strip of bounded basis and unlimited height. The objective is to pack all items into a strip of minimal height. In the knapsack packing setting the given space Q$Q$ is a single, usually unit sized bin and the items have associated profits _pi$p_i$. The goal is to maximize the profit of a selection of items that can be packed into the bin.     

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.     

State-complexity hierarchies of uniform languages of alphabet-size length

We study the state complexity of certain simple languages. If A$A$ is an alphabet of k$k$ letters, then a k$k$-language   is a nonempty set of words of length k$k$, that is, a uniform language of length k$k$. We show that the minimal state complexity of a k$k$-language is k+2$k+2$, and the maximal, (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. We prove constructively that, for every i$i$ between the minimal and maximal bounds, there is a language of state complexity i$i$. We introduce a class of automata accepting sets of words that are permutations of A$A$; these languages define a complete hierarchy of complexities between k²−k+3$k^2-k+3$ and 2^k+1$2^k+1$. The languages of another class of automata, based on k$k$-ary trees, define a complete hierarchy of complexities between 2^k+1$2^k+1$ and (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. This provides new examples of uniform languages of maximal complexity.     

On the size of Boyer–Moore automata

In this work we study the size of Boyer–Moore automata introduced in Knuth, Morris & Pratt’s famous paper on pattern matching. We experimentally show that a finite class of binary patterns produce very large Boyer–Moore automata, and find one particular case which we conjecture, generates automata of size Ω(m⁶)$\Omega \left(m^6\right)$. Further experimental results suggest that the maximal size could be a polynomial of O(m⁷)$O\left(m^7\right)$, or even an exponential O(2^0.4m)$O\left(2^{0.4m}\right)$, where m$m$ is the length of the pattern.