Topological tunnelling with dynamical overlap fermions

Tunnelling between different topological sectors with dynamical chiral fermions is difficult because of a poor mass scaling of the pseudo-fermion estimate of the determinant. For small fermion masses it is virtually impossible using standard methods. However, by projecting out the small Wilson eigenvectors from the overlap operator, and treating the correction determinant exactly, we can significantly increase the rate of topological sector tunnelling and reduce substantially the auto-correlation time. We present and compare a number of different approaches, and advocate a method which allows topological tunnelling even at low mass with little addition to the computational cost.     

An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case

We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points,within a given set of points in the XY-plane.For this version of the algorithm we show that only two pairwise comparisons are required in the combine step,for each point that lies in the 2δ-wide vertical slab.The correctness of the algorithm is shown for all Minkowski distances with p 1.We also show empirically that,although the time complexity of the algorithm is still O(n lg n),the reduction in the total number of comparisons leads to a significant reduction in the total execution time,for inputs with size sufficiently large.     

The k closest pairs in spatial databases

We provide in this article a branch-and-bound algorithm that solves the problem of finding the k closest pairs of points (p,q), p?∈?P,q?∈?Q, considering two sets of points in the euclidean plane P,Q stored in external memory assuming that only one of the sets has a spatial index. This problem arises naturally in many scenarios, for instance when the set without an index is the answer to a spatial query. The main idea of our algorithm is to partition the space occupied by the set without an index into several cells or subspaces and to make use of the properties of a set of metrics defined on two Minimum Bounding Rectangles (MBRs). We evaluated our algorithm for different values of k by means of a series of experiments that considered both synthetical and real world datasets. We compared the performance of our algorithm with that of techniques that either assume that both datasets have a spatial index or that none has an index. The results show that our algorithm needs only between a 0.3 and a 35 % of the disk accesses required by such techniques. Our algorithm also shows a good scalability, both in terms of k and of the size of the data set.     

Hybrid bee colony optimization for examination timetabling problems

Swarm intelligence is a branch of artificial intelligence that focuses on the actions of agents in self-organized systems. Researchers have proposed a bee colony optimization (BCO) algorithm as part of swarm intelligence. BCO is a meta-heuristic algorithm based on the foraging behavior of bees. This study presents a hybrid BCO algorithm for examination timetabling problems. Bees in the BCO algorithm perform two main actions: forward pass and backward pass. Each bee explores the search space in forward pass and then shares information with other bees in the hive in backward pass. This study found that a bee decides to be either a recruiter that searches for a food source or a follower that selects a recruiter bee to follow on the basis of roulette wheel selection. In forward pass, BCO is supported along with other local searches, including the Late Acceptance Hill Climbing and Simulated Annealing algorithms. We introduce three selection strategies (tournament, rank and disruptive selection strategies) for the follower bees to select a recruiter to maintain population diversity in backward pass. The disruptive selection strategy outperforms tournament and rank selections. We also introduce a self-adaptive mechanism to select a neighborhood structure to enhance the neighborhood search. The proposed algorithm is evaluated against the latest methodologies in the literature with respect to two standard examination timetabling problems, namely, uncapacitated and competition datasets. We demonstrate that the proposed algorithm produces one new best result on uncapacitated datasets and comparable results on competition datasets.     

Optimal Routing Algorithms for a Class of Cylindrical Banyan Multicomputers

The cylindrical banyan network is a variation of the classical banyan network in two ways: (1) each node is a processor with a switch, and (2) every pair of nodes at the two ends is merged. We present a routing algorithm for the cylindrical banyan network, and show it is optimal in terms of the path length. We also show that for the cylindrical banyan network containing L levels with 2^L processors at each level (i.e., containing L2^L processors in total), the worst case path length between any two nodes is 1.5L. We discuss a generalization of the cylindrical banyan network and an optimal routing algorithm for it. Our routing algorithms are distributed, and so can be executed locally at each processor.     

Implicitization of a General Union of Parametric Varieties

We reconduct the computation of the equations defining a union V of parametric varieties, up to a given degree d, to the computation of the equations, of degree  ≤ d, vanishing on a finite set of points of V. If V is general this gives a new algorithm for implicitizing V. We have compared the implementation of this algorithm with the Hilbert-driven elimination algorithm included in the software packages CoCoA 3.7 and Singular 1.2, obtaining significant time savings. Moreover, the implementation of the algorithm leads to two intriguing conjectures on the natural number of generators of the union of general parametric curves or surfaces.     

Finding approximate palindromes in strings

We introduce a novel definition of approximate palindromes in strings, and provide an algorithm to find all maximal approximate palindromes in a string with up to k errors. Our definition is based on the usual edit operations of approximate pattern matching, and the algorithm we give, for a string of size n on a fixed alphabet, runs in O(k²n) time. We also discuss two implementation-related improvements to the algorithm, and demonstrate their efficacy in practice by means of both experiments and an average-case analysis.     

Online scheduling of two job types on a set of multipurpose machines with unit processing times

We study a problem of scheduling a set of n jobs with unit processing times on a set of m multipurpose machines in which the objective is to minimize the makespan. It is assumed that there are two different job types, where each job type can be processed on a unique subset of machines. We provide an optimal offline algorithm to solve the problem in constant time and an online algorithm with a competitive ratio that equals the lower bound. We show that the worst competitive ratio is obtained for an inclusive job-machine structure in which the first job type can be processed on any of the m machines while the second job type can be processed only on a subset of m/2 machines. Moreover, we show that our online algorithm is 1-competitive if the machines are not flexible, i.e., each machine can process only a single job type.     

On-line machine covering on two machines with local migration

We study an on-line machine covering problem, in which jobs arrive one by one and their processing times are known upon their arrival, and jobs are allowed to migrate between machines when a new job is added in the system. However, the total processing time of migration induced by an incoming job is bounded by a constant factor β times the processing time of the incoming job. The objective is to maximize the minimum machine load. In this paper, we present an on-line algorithm with competitive ratio 6/5 for the two identical machines case with β=1. Moreover, the presented on-line algorithm is only a local migration, that is, when one job is assigned to machine i, only the jobs on machine i are allowed to migrate. We also show that the provided algorithm is a best possible on-line algorithm in the sense of local migration.     

Two-machine flow-shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow-shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is NP-hard and for its solution we provide two different approximation algorithms, a pseudo-polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto-optimal points (this problem is NP-hard due to the NP-hardness of the same problem variation on a single machine [20]). We show that this problem can be solved in pseudo-polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most (1+?)R and a makespan value of at most (1+?)K. This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.     

Clear and smooth path planning

One of the challenging problems in motion planning is finding an efficient path for a robot in different aspects such as length, clearance and smoothness. We formulate this problem as two multi-objective path planning models with the focus on robot's energy consumption and path's safety. These models address two five- and three-objectives optimization problems. We propose an evolutionary algorithm for solving the problems. For efficient searching and achieving Pareto-optimal regions, in addition to the standard genetic operators, a family of path refiner operators is introduced. The new operators play a local search role and intensify power of the algorithm in both explorative and exploitative terms. Finally, we verify the models and compare efficiency of the algorithm and the refiner operators by other multi-objective algorithms such as strength Pareto evolutionary algorithm 2 and multi-objective particle swarm optimization on several complicated path planning test problems.     

Improving clustering by learning a bi-stochastic data similarity matrix

An idealized clustering algorithm seeks to learn a cluster-adjacency matrix such that, if two data points belong to the same cluster, the corresponding entry would be 1; otherwise, the entry would be 0. This integer (1/0) constraint makes it difficult to find the optimal solution. We propose a relaxation on the cluster-adjacency matrix, by deriving a bi-stochastic matrix from a data similarity (e.g., kernel) matrix according to the Bregman divergence. Our general method is named the Bregmanian Bi-Stochastication (BBS) algorithm. We focus on two popular choices of the Bregman divergence: the Euclidean distance and the Kullback?CLeibler (KL) divergence. Interestingly, the BBS algorithm using the KL divergence is equivalent to the Sinkhorn?CKnopp (SK) algorithm for deriving bi-stochastic matrices. We show that the BBS algorithm using the Euclidean distance is closely related to the relaxed k-means clustering and can often produce noticeably superior clustering results to the SK algorithm (and other algorithms such as Normalized Cut), through extensive experiments on public data sets.     

Submodular fractional programming for balanced clustering

We address the balanced clustering problem where cluster sizes are regularized with submodular functions. The objective function for balanced clustering is a submodular fractional function, i.e., the ratio of two submodular functions, and thus includes the well-known ratio cuts as special cases. In this paper, we present a novel algorithm for minimizing this objective function (submodular fractional programming) using recent submodular optimization techniques. The main idea is to utilize an algorithm to minimize the difference of two submodular functions, combined with the discrete Newton method. Thus, it can be applied to the objective function involving any submodular functions in both the numerator and the denominator, which enables us to design flexible clustering setups. We also give theoretical analysis on the algorithm, and evaluate the performance through comparative experiments with conventional algorithms by artificial and real datasets.     

An algorithm for k-anonymous microaggregation and clustering inspired by the design of distortion-optimized quantizers

We present a multidisciplinary solution to the problems of anonymous microaggregation and clustering, illustrated with two applications, namely privacy protection in databases, and private retrieval of location-based information. Our solution is perturbative, is based on the same privacy criterion used in microdata k-anonymization, and provides anonymity through a substantial modification of the Lloyd algorithm, a celebrated quantization design algorithm, endowed with numerical optimization techniques.Our algorithm is particularly suited to the important problem of k-anonymous microaggregation of databases, with a small integer k representing the number of individual respondents indistinguishable from each other in the published database. Our algorithm also exhibits excellent performance in the problem of clustering or macroaggregation, where k may take on arbitrarily large values. We illustrate its applicability in this second, somewhat less common case, by means of an example of location-based services. Specifically, location-aware devices entrust a third party with accurate location information. This party then uses our algorithm to create distortion-optimized, size-constrained clusters, where k nearby devices share a common centroid location, which may be regarded as a distorted version of the original one. The centroid location is sent back to the devices, which use it when contacting untrusted location-based information providers, in lieu of the exact home location, to enforce k-anonymity.We compare the performance of our novel algorithm to the state-of-the-art microaggregation algorithm MDAV, on both synthetic and standardized real data, which encompass the cases of small and large values of k. The most promising aspect of our proposed algorithm is its capability to maintain the same k-anonymity constraint, while outperforming MDAV by a significant reduction in data distortion, in all the cases considered.     

An Efficient Processor Allocation Algorithm Using Two-Dimensional Packing

Mesh is one of the most widely used interconnection networks for multiprocessor systems. In this paper, we propose an approach to partition a given mesh intomsubmeshes which can be allocated tomtasks with grid structures. We adapt two-dimensional packing to solve the submesh allocation problem. Due to the intractability of the two-dimensional packing problem, finding an optimal solution is computationally infeasible. We develop an efficient heuristic packing algorithm called TP-heuristic. Allocating a submesh to each task is achieved using the results of packing. We propose two different methods called uniform scaling and nonuniform scaling. Experiments were carried out to test the accuracy of solutions provided by our allocation algorithm.     

A strongly competitive randomized paging algorithm

Thepaging problem is that of deciding which pages to keep in a memory ofk pages in order to minimize the number of page faults. We develop thepartitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor ofH _k of optimum. (H _k is thekth harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.     

Solving the generalized eigenvalue problem on a synchronous linear processor array

We present a parallel method to solve the generalized eigenvalue problem on a linear array of processors, each connected to their nearest neighbors and operating synchronously. We also include a wrap-around connection from end to end. Our method is based on the well-known QZ algorithm of Moler and Stewart, which simultaneously reduces two n × n matrices to upper triangular form by orthogonal or unitary transformations. We show how this algorithm may be partitioned and distributed of n + 1 processors, achieving a speed-up over the serial algorithm of O(n). We use the concept of windows to describe the action of each processor at each step. We show how to incorporate singles shifts, and how to apply orthogonal plane rotations on either side of a matrix without the need to transpose the matrix itself.     

New solutions for disjoint paths in P systems

We propose four fast synchronous distributed message-based algorithms, to identify maximum cardinality sets of edge- and node-disjoint paths, between a source node and a target node in a digraph. Previously, Dinneen et?al. presented two algorithms, based on the classical distributed depth-first search (DFS), which run in O(mf) steps, where m is the number of edges and f is the number of disjoint paths. Combining Cidon??s distributed DFS and our new result, Theorem 3, we propose two improved DFS-based algorithms, which run in O(nf) steps, where n is the number of nodes. We also present improved versions of our two breadth-first search (BFS) based algorithms, with the same complexity upperbound, O(nf). Empirically, for a large set of randomly generated digraphs, our DFS-based edge-disjoint algorithm is 39?% faster than Dinneen et?al.??s edge-disjoint algorithm and our BFS-based edge-disjoint algorithm is 80?% faster. All these improved algorithms have been inspired and guided by a P system modelling exercise, but are suitable for any distributed implementation.     

A two-phase algorithm for the biobjective integer minimum cost flow problem

We present an algorithm to compute a complete set of efficient solutions for the biobjective integer minimum cost flow problem. We use the two phase method, with a parametric network simplex algorithm in phase 1 to compute all non-dominated extreme points. In phase 2, the remaining non-dominated points (non-extreme supported and non-supported) are computed using a k best flow algorithm on single-objective weighted sum problems.     

Critical slowing-down in SU(2) Landau-gauge-fixing algorithms at β=∞

We evaluate numerically and analytically the dynamic critical exponent z for five gauge-fixing algorithms in SU(2) lattice Landau-gauge theory by considering the case β=∞. Numerical data are obtained in two, three and four dimensions. Results are in agreement with those obtained previously at finite β in two dimensions. The theoretical analysis, valid for any dimension d, helps us clarify the tuning of these algorithms. We also study generalizations of the overrelaxation algorithm and of the stochastic overrelaxation algorithm and verify that we cannot have a dynamic critical exponent z smaller than 1 with these local algorithms. Finally, the analytic approach is applied to the so-called λ-gauges, again at β=∞, and verified numerically for the two-dimensional case.