Algorithms for solving linear systems over cyclotomic fields

We consider the problem of solving a linear system Ax=b$Ax=b$ over a cyclotomic field. Cyclotomic fields are special in that we can easily find a prime p$p$ for which the minimal polynomial m(z)$m\left(z\right)$ for the field factors into a product of distinct linear factors. This makes it possible to develop fast modular algorithms.     

Efficient algorithms for center problems in cactus networks

Efficient algorithms for solving the center problems in weighted cactus networks are presented. In particular, we have proposed the following algorithms for the weighted cactus networks of size n$n$: an O(nlogn)$O(nlogn)$ time algorithm to solve the 1-center problem, and an O(nlog³n)$O\left(n{log}^{3}n\right)$ time algorithm to solve the weighted continuous 2-center problem. We have also provided improved solutions to the general p$p$-center problems in cactus networks. The developed ideas are then applied to solve the obnoxious 1-center problem in weighted cactus networks.     

A new self-stabilizing maximal matching algorithm

The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from O(n²)$O\left(n^2\right)$ and O(δm)$O\left(\delta m\right)$ to O(m)$O\left(m\right)$ where n$n$ is the number of processes, m$m$ is the number of edges, and δ$\delta$ is the maximum degree in the graph.     

Performance tradeoffs in structured peer to peer streaming

We consider the following basic question: a source node wishes to stream an ordered sequence of packets to a collection of receivers, which are in K$K$ clusters. A node may send a packet to another node in its own cluster in one time step and to a node in a different cluster in _Tc$T_c$ time steps (_Tc>1)$(T_c>1)$. Each cluster has two special nodes. We assume that the source and the special nodes in each cluster have a higher capacity and thus can send multiple packets at each step, while all other nodes can both send and receive a packet at each step. We construct two (intra-cluster) data communication schemes, one based on multi-trees (using a collection of d$d$-ary interior-disjoint trees) and the other based on hypercubes. The multi-tree scheme sustains streaming within a cluster with O(dlogN)$O(dlogN)$ maximum playback delay and O(dlogN)$O(dlogN)$ size buffers, while communicating with O(d)$O\left(d\right)$ neighbors, where N$N$ is the maximum size of any cluster. We also show that this protocol is optimal when d=2$d=2$ or 3. The hypercube scheme sustains streaming within a cluster, with O(log²(N))$O\left({log}^2\left(N\right)\right)$ maximum playback delay and O(1)$O\left(1\right)$ size buffers, while communicating with O(log(N))$O(log\left(N\right))$ neighbors, for arbitrary N$N$. In addition, we extend our multi-tree scheme to work when receivers depart and arrive over time. We also evaluate our dynamic schemes using simulations.     

Scheduling light-trails on WDM rings

We consider the problem of scheduling communication on optical WDM (wavelength division multiplexing) networks using the light-trails technology. We seek to design scheduling algorithms such that the given transmission requests can be scheduled using a minimum number of wavelengths (optical channels). We provide algorithms and close lower bounds for two versions of the problem on an n$n$ processor linear array/ring network. In the stationary   version, the pattern of transmissions (given) is assumed to not change over time. For this, a simple lower bound is c$c$, the congestion or the maximum total traffic required to pass through any link. We give an algorithm that schedules the transmissions using O(c+logn)$O(c+logn)$ wavelengths. We also show a pattern for which Ω(c+logn/loglogn)$\Omega (c+logn/loglogn)$ wavelengths are needed. In the on-line   version, the transmissions arrive and depart dynamically, and must be scheduled without upsetting the previously scheduled transmissions. For this case we give an on-line algorithm which has competitive ratio Θ(logn)$\Theta (logn)$. We show that this is optimal in the sense that every on-line algorithm must have competitive ratio Ω(logn)$\Omega (logn)$. We also give an algorithm that appears to do well in simulations (for the classes of traffic we consider), but which has competitive ratio between Ω(log²n/loglogn)$\Omega ({log}^{2}n/loglogn)$ and O(log²n)$O\left({log}^{2}n\right)$. We present detailed simulations of both our algorithms.     

Claw finding algorithms using quantum walk

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f$f$ and g$g$, with domain sizes N$N$ and M$M$(N≤M)$(N\le M)$, respectively, and the same range, the goal of the problem is to find x$x$ and y$y$ such that f(x)=g(y)$f\left(x\right)=g\left(y\right)$. This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of k$k$ functions for any constant integer k>1$k>1$, where the domain sizes of the functions may be different.     

Online vector scheduling and generalized load balancing

We give a polynomial time reduction from the vector scheduling problem (VS) to the generalized load balancing problem (GLB). This reduction gives the first non-trivial online algorithm for VS where vectors come in an online fashion. The online algorithm is very simple in that each vector only needs to minimize the _Lln(md)$L_{ln\left(md\right)}$ norm of the resulting load when it comes, where m$m$ is the number of partitions and d$d$ is the dimension of vectors. It has an approximation bound of elog(md)$elog\left(md\right)$, which is in O(ln(md))$O(ln\left(md\right))$, so it also improves the O(ln²d)$O\left({ln}^{2}d\right)$ bound of the existing polynomial time algorithm for VS. Additionally, the reduction shows that GLB does not have constant approximation algorithms that run in polynomial time unless P=NP$P=NP$.     

Distributed attitude synchronization control of multi-agent systems with switching topologies

This paper addresses the attitude synchronization problem in multi-agent systems with directed and switching interconnection topologies. Two cases for the synchronization problem are discussed under different assumptions about the measurable information. In the first case the agents can measure their rotations relative to a global reference coordinate frame, whilst in the second case they can only measure the relative rotations between each other. Two intuitive distributed control laws based on the axis–angle representations of the rotations are proposed for the two cases, respectively. The invariance of convex balls in SO(3)$SO\left(3\right)$ is guaranteed. Moreover, attitude synchronization is ensured under the well-known mild switching assumptions, the joint strong connection for the first case and joint quasi-strong connection for the second case. To show the effectiveness of the proposed control schemes, illustrative examples are provided.     

A parameterized view on matroid optimization problems

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n^O(k)$n^{O\left(k\right)}$ time brute force algorithm for finding a k$k$-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅n^O(1)$f\left(k\right)\cdot n^{O\left(1\right)}$) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?$?$, then we can determine in randomized time f(k,?)⋅n^O(1)$f(k,?)\cdot n^{O\left(1\right)}$ whether there is an independent set that is the union of k$k$ blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k$k$-element set in the intersection of ?$?$ matroids, or finding k$k$ terminals in a network such that each of them can be connected simultaneously to the source by ?$?$ disjoint paths.     

g_contacts: Fast contact search in bio-molecular ensemble data

Short-range interatomic interactions govern many bio-molecular processes. Therefore, identifying close interaction partners in ensemble data is an essential task in structural biology and computational biophysics. A contact search can be cast as a typical range search problem for which efficient algorithms have been developed. However, none of those has yet been adapted to the context of macromolecular ensembles, particularly in a molecular dynamics (MD) framework. Here a set-decomposition algorithm is implemented which detects all contacting atoms or residues in maximum O(Nlog(N))$O(Nlog\left(N\right))$ run-time, in contrast to the O(N²)$O\left(N^2\right)$ complexity of a brute-force approach.     

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.     

Efficient transformation of distance-2 self-stabilizing algorithms

Self-stabilizing algorithms for optimization problems can often be solved more easily using the distance-two model in which each vertex can instantly see the state information of all vertices up to distance two. This paper presents a new technique to emulate algorithms for the distance-two model on the distance-one model using the distributed scheduler with a slowdown factor of O(m)$O\left(m\right)$ moves. Up until now the best transformer had a slowdown factor of O(n²m)$O\left(n^{2}m\right)$ moves. The technique is used to derive improved self-stabilizing algorithms for several graph domination problems. The paper also introduces a generalization of the distance-two model allowing a more space efficient transformer.     

Grid-based lattice summation of electrostatic potentials by assembled rank-structured tensor approximation

Our recent method for low-rank tensor representation of sums of the arbitrarily positioned electrostatic potentials discretized on a 3D Cartesian grid reduces the 3D tensor summation to operations involving only 1D vectors however retaining the linear complexity scaling in the number of potentials. Here, we introduce and study a novel tensor approach for fast and accurate assembled summation of a large number of lattice-allocated potentials represented on 3D N×N×N$N\times N\times N$ grid with the computational requirements only weakly dependent   on the number of summed potentials. It is based on the assembled low-rank canonical tensor representations of the collected potentials using pointwise sums of shifted canonical vectors representing the single generating function, say the Newton kernel. For a sum of electrostatic potentials over L×L×L$L\times L\times L$ lattice embedded in a box the required storage scales linearly in the 1D grid-size, O(N)$O\left(N\right)$, while the numerical cost is estimated by O(NL)$O\left(NL\right)$. For periodic boundary conditions, the storage demand remains proportional to the 1D grid-size of a unit cell, n=N/L$n=N/L$, while the numerical cost reduces to O(N)$O\left(N\right)$, that outperforms the FFT-based Ewald-type summation algorithms of complexity O(N³logN)$O(N^{3}logN)$. The complexity in the grid parameter N$N$ can be reduced even to the logarithmic scale O(logN)$O(logN)$ by using data-sparse representation of canonical N$N$-vectors via the quantics tensor approximation. For justification, we prove an upper bound on the quantics ranks for the canonical vectors in the overall lattice sum. The presented approach is beneficial in applications which require further functional calculus with the lattice potential, say, scalar product with a function, integration or differentiation, which can be performed easily in tensor arithmetics on large 3D grids with 1D cost. Numerical tests illustrate the performance of the tensor summation method and confirm the estimated bounds on the tensor ranks.     

Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system

This study addresses the identical parallel machine scheduling problem in which the total earliness and tardiness about a common due date are minimized subject to minimum total flowtime, P∥(E+T)/∑_Ci$P\parallel (E+T)/\sum C_i$. The problem is demonstrated to be transformed into a simplified version of the parallel machine problem with the objective of minimizing makespan subject to minimum total flowtime, P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$. Several properties are considered to solve optimally the restricted version of the problem. A streamlined binary integer programming model is developed to solve the P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$ problem and the P∥(E+T)/∑_Ci$P\parallel (E+T)/\sum C_i$ problem. Computational experiments indicate that the binary integer programming model is superior to the existing optimization algorithm for the P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$ problem in the literature.