Search

Approximate Matrix Multiplication (AMM) has emerged as a useful and computationally inexpensive substitute for actual multiplication of large matrices. Randomized as well as deterministic solutions to AMM were provided in the past. The latest work provides a deterministic algorithm that solves AMM more accurately than the other works. It is a streaming algorithm that is both fast and accurate. But, it is less robust to noise and is also liable to have less than optimal performance in the presence of concept drift in the input matrices. We propose an algorithm that is more accurate, robust to noise, invariant to concept drift in the data, while having almost the same running time as the state-of-the-art algorithm. We also prove that theoretical guarantees exist for the proposed algorithm. An empirical performance improvement of up to 90 % is obtained over the previous algorithm. We also propose a general framework for parallelizing the proposed algorithm. The two parallelized versions of the algorithm achieve up to 1.9 x and 3.6 x speedups over the original version of the proposed algorithm.

This paper proposed an improved incremental smoothing and mapping (iSAM) which combines flexible re-linearization threshold with error learning model to improve the efficiency and accuracy of navigation for autonomous underwater vehicle (AUV). The flexible threshold of the proposed method, which can avoid periodic re-linearization of iSAM, is controlled by adaptive threshold. Through the use of flexible re-linearization, the proposed method can reduce the running time and carry out re-linearization timely. Simultaneously, for the first time, the proposed method takes advantages of the fast training time of hidden-layer neural networks and Gaussian Process Regression which is more suitable for non-linearity to get error learning model for iSAM. The proposed method can achieve better accuracy with only a rough model and can be easily transplanted to other systems without cumbersome calculations of the precise model. Our algorithm has been demonstrated by a range of simulated and real datasets, especially in practical application it outperforms current available iSAM algorithms in efficiency and accuracy. The RMSE of proposed method increases by 21.7% and efficiency also has been improved by 56% than iSAM2 in practical application for AUV.

The different communications of users in social networks play a key role in effect to each other. The effect is important when they can achieve their goals through different communications. Studying the effect of specific users on other users has been modeled on the influence maximization problem on social networks. To solve this problem, different algorithms have been proposed that each of which has attempted to improve the influence spread and running time than other algorithms. Due to the lack of a review of the meta-heuristic algorithms for the influence maximization problem so far, in this paper, we first perform a comprehensive categorize of the presented algorithms for this problem. Then according to the efficient results and significant progress of the meta-heuristic algorithms over the last few years, we describe the comparison, advantages, and disadvantages of these algorithms.

Considering the problems of communication overhead between nodes and the challenges brought by large-scale complex network in distributed system cluster management, we propose a local community detection algorithm in complex network called FLCDA (Fast Local Community Detection Algorithm). FLCDA can detect communities in a large-scale complex network on a single PC. The algorithm uses a Parallel Sliding Windows (PSW) method to break a large-scale network into smaller sub-networks, and load sub-network into a PC memory. This method conforms to the local characteristics of the community. FLCDA first finds out disjoint Maximum Influence k-clique in each sub-network, and then assigns the same label and weight to all nodes in the same Maximum Influence k-clique. These labels and weights are used as seeds at the label propagation phase of FLCDA. During the labeling propagation phase, FLCDA applies a synchronous update strategy while removes meaningless labels after each iteration. When all node labels are updated, the update process will be ended. This method can reduce the calculation cost and improve the stability. The experiment results show that non-parameter FLCDA can self-adaptively detect communities on various scales and types of complex networks. By comparing with other algorithms, FLCDA has gained higher community detection accuracy and less running time. Therefore, FLCDA algorithm can be better adapted to community detection in real complex networks without prior knowledge.

The heuristic algorithms are often used to find solutions to real complex world problems. In this paper, the Social Spider Algorithm (SSA) and Social Spider Optimization (SSO) which are heuristic algorithms created upon spider behaviors are considered. Performances of both algorithms are compared with each other from six different items. These are; fitness values of spider population which are obtained in different dimensions, number of candidate solution obtained in each iteration, the best value of candidate solutions obtained in each iteration, the worst value of candidate solutions obtained in each iteration, average fitness value of candidate solutions obtained in each iteration and running time of each iteration. Obtained results of SSA and SSO are applied to the Wilcoxon signed-rank test. Various unimodal, multimodal, and hybrid standard benchmark functions are studied to compare each other with the performance of SSO and SSA. Using these benchmark functions, performances of SSO and SSA are compared with well-known evolutionary and recently developed methods in the literature. Obtained results show that both heuristic algorithms have advantages to another from different aspects. Also, according to other algorithms have good performance.

Natural language processing (NLP), as a theory-motivated computational technique, has extensive applications. Automated test case generation based on path coverage, which is a popular structural testing activity, can automatically reveal logic defects that exist in NLP programs and can save testing consumption. NLP programs have many paths that can only be covered by specific input variables. This feature makes conventional search-based algorithm very difficult covering all possible paths in NLP programs. A strategy is required for improving the search ability of search-based algorithms. In this paper, we propose a scatter search strategy to automatically generate test cases for covering all possible paths of NLP programs. The scatter search strategy empowers search-based algorithms to explore all input variables and cover the paths that require specific input variables within a small amount of test cases. The experiment results show that the proposed scatter search strategy can quickly cover the paths, which requires specific input variables. Many test cases and running time consumptions will be saved when search-based algorithms combine with scatter search strategy.

Researchers have established a classification model based on tear Raman spectroscopy combined with machine learning classification algorithms, which realizes rapid noninvasive classification of cerebral infarction and cerebral ischemia, which is of great significance for clinical medical diagnosis. Through spectral data analysis, it is found that there are differences in the content of tyrosine, phenylalanine, and carotenoids in the tears of patients with cerebral ischemia and patients with cerebral infarction. We try to establish a classification model for rapid noninvasive screening of cerebral infarction and cerebral ischemia through these differences. The experiment has four parts, including normalization, data enhancement, feature extraction, and data classification. The researchers combined three feature extraction methods with four machine classification models to build a total of 12 classification models. Integrating 8 classification criteria, the classification accuracy of all models is above 85%, especially PLS-PNN has achieved 100% accuracy and better running time. The experimental results show that tear Raman spectroscopy combined with machine learning classification model has a good effect on the screening of cerebral ischemia and cerebral infarction, which is conducive to the noninvasive and rapid clinical diagnosis of cerebrovascular diseases in the future.

We propose an integrated path planning method for multiple automated guided vehicles performing logistics delivery within a real-world warehouse environment considering obstacles. By applying it on each vehicle, this proposed method enables the vehicle the vehicles have the capabilities for autonomous path planning. The path planning consists of three parts, K-means algorithm based task points clustering, genetic algorithm based task points ordering, and the probabilistic road map based best path search. Vehicle conflict resolution is depending on implementing the probabilistic road map construction considering the realistic map with obstacles. The simulations result validate that the clustering and ordering are necessary for the path planning, both the path planning time and the Automated guided vehicles (AGVs) running time can be dramatically reduced.

This paper presents new algorithms for Field of Vision (FOV) computation which improve on existing work at high resolutions. FOV refers to the set of locations that are visible from a specific position in a scene of a computer game. We review existing algorithms for FOV computation, describe their limitations, and present new algorithms which aim to address these limitations. We first present an algorithm which makes use of spatial data structures in a way which is new for FOV calculation. We then present a novel technique which updates a previously calculated FOV, rather than re-calculating an FOV from scratch. We compare our algorithms to existing FOV algorithms and show they provide substantial improvements to running time. Our algorithms provide the largest improvement over existing FOV algorithms at highresolutions, thus allowing the possibility of the creation of high resolution FOV-based video games.

In order to improve the global search ability of K-means algorithm and the clustering effect, a K-means method based on the approximate backbone and the shuffled frog leaping algorithm was proposed. Firstly, the classic iterative formula of the K-means algorithm is replaced by the classic shuffled frog leaping algorithm to obtain better clustering results. Secondly, the K-means algorithm based on the approximate backbone and the shuffled frog leaping algorithm is used for the obtained clustering results. Instead of searching for cluster centers, the cluster division is directly modified. Finally, the experimental results on the UCI dataset show that, the running time of the improved clustering algorithm is shorter than that based on the shuffled frog leaping algorithm only, and clustering results obtained by using the improved clustering algorithm are better than those of other algorithms. In addition, the paper uses the improved clustering algorithm to preprocess medical fundus images to optimize the effect of vascular cutting.

Effective chiller fault diagnosis is of great importance for maintaining a better service and energy efficiency. Deep learning proficiently solves some problems challenging Artificial Intelligence and becomes one of the excellent candidates for fault diagnosis recently. This study proposes a novel fault diagnosis strategy for a chiller, which merges simulated annealing (SA) into a deep neural network (DNN) to obtain effective, efficient, and stable performance. The proposed SA-DNN strategy is carefully compared with DNN and back-propagation (BP) network. The results show that SA-DNN enhances the diagnostic accuracy, shortens the running time, and greatly improves the model stability. The optimal network structure has 2 hidden layers (HL) with each layer 64 nodes, and the overall diagnostic accuracy for seven typical faults attains 99.30%. The nodes in the first HL are proved to be dominant over those in the second or behind because the mapping of the second can hardly make corrections if that of the first is deformed already. The global faults are hard to be diagnosed due to the global effect, but the proposed strategy achieves satisfactory results with the highest individual accuracy reaching 99.79% for excess oil and the lowest 97.52% for refrigerant leakage. The features used for diagnosis have an influence on the accuracy of the proposed method.

Based on the similarity of the community detection methods, the Givern-Newman (GN) algorithm is fast and accurate but has a higher running time. In order to improve the efficiency of GN Algorithm, this study presents a semi-supervised GN algorithm based on node similarity. By making full use of the constraint set of the prior knowledge must-link and cannot-link, the prior information is extended by the derived rules, and the extended information is verified by the method of distance measurement. Using new annealing maximisation algorithm to calculate node similarity iteratively, and validated using artificial and real networks. It proves that the proposed algorithm reduces the GN algorithm's running time and improves efficiency.

The optimization of the main key compression bottlenecks of the supersingular isogeny key encapsulation mechanism (SIKE) has been a target of research in the last few years. Significant improvements were introduced in the recent works of Costello et al. (EUROCRYPT’2017) and Zanon et al. (PQCrypto’2018; IEEE ToC’2018). The combination of the techniques in Zanon et al. (PQCrypto’2018; IEEE ToC’2018) reduced the running time of binary torsion basis generation in decompression by a factor of 29 compared to previous work. On the other hand, generating such a basis still takes almost a million cycles on an Intel Core i5-6267U Skylake. In this paper, we continue the work of Zanon et al. (IEEE ToC’2018) and introduce a technique that drops the complexity of binary torsion basis generation by a factor $$\log p$$ in the number of underlying field multiplications. In particular, our experimental results show that a basis can be generated in about 1300 cycles, attaining an improvement by a factor more than 600. Although this result eliminates one of the key compression bottlenecks, many other bottlenecks remain. In addition, we give further improvements for the ternary torsion generation with significant impact on the related decompression procedure. Moreover, a new trade-off between ciphertext sizes versus decapsulation speed and storage is introduced and achieves a 1.7 times faster decapsulation.

The naïve algorithm for generating nearest-neighbour models determines the distance between every pair of nodes, resulting in quadratic running time. Such time complexity is common among spatial problems and impedes the generation of larger spatial models. In this article, an improved algorithm for the Mocnik model, an example of nearest-neighbour models, is introduced. Instead of solving k nearest-neighbour problems for each node (k dynamic in the sense that it varies among the nodes), the improved algorithm presented exploits the notion of locality through introducing a corresponding spatial index, resulting in a linear average-case time complexity. This makes possible to generate very large prototypical spatial networks, which can serve as testbeds to evaluate and improve spatial algorithms, in particular, with respect to the optimization of algorithms towards big geospatial data.

Welcome to Drill Bits , a new column about programming. This inaugural episode shows how graph search algorithms can avoid unnecessary work. A simple modification to classic breadth-first search improves the lower bound on its running time: Whereas classic BFS always requires time proportional to the number of vertices plus the number of edges, the improved "Efficient BFS" sometimes runs in time proportional to the number of vertices alone. Both asymptotic analysis and experiments show that Efficient BFS can be much faster than classic BFS. All software used in the experiments is available for download, and suggestions for further explorations are provided.

Recently, iteratively reweighted methods have attracted much interest in compressed sensing, outperforming their unweighted counterparts in most cases. In these methods, decision variables and weights are optimized alternatingly, or decision variables are optimized under heuristically chosen weights. In this paper, we present a novel weighted $l_1$-norm minimization problem for the sparsest solution of underdetermined linear equations. We propose an iteratively weighted thresholding method for this problem, wherein decision variables and weights are optimized simultaneously. Furthermore, we prove that the iteration process will converge eventually. Using the homotopy technique, we enhance the performance of the iteratively weighted thresholding method. Finally, extensive computational experiments show that our method performs better in terms of both running time and recovery accuracy compared with some state-of-the-art methods.

This paper simulates the cuckoo incubation process and flight path to optimize the Wavelet Neural Network (WNN) model, and proposes a parking prediction algorithm based on WNN and improved Cuckoo Search (CS) algorithm. First, the initialization parameters are provided to optimize the WNN using the improved CS. The traditional CS algorithm adopts the strategy of overall update and evaluation, but does not consider its own information, so the convergence speed is very slow. The proposed algorithm employs the evaluation strategy of group update, which not only retains the advantage of fast convergence of the dimension-by-dimension update evaluation strategy, but also increases the mutual relationship between the nests and reduces the overall running time. Then, we use the WNN model to predict parking information. The proposed algorithm is compared with six different heuristic algorithms in five experiments. The experimental results show that the proposed algorithm is superior to other algorithms in terms of running time and accuracy.

In the present study, we identify a new type of extended metrics space, i.e. generalized quasi-partial metric space and utilize it to introduce new results of fixed point for contractive monotone mappings. Some interesting examples are also presented. We apply the fixed point results to the complexity of computer algorithms and analyze their running time.

The problem is, given a set of n vectors in a d-dimensional normed space, find a subset with the largest length of the sum vector. We prove that, in the case of the l p norm, the problem is APX-complete for any p ∈ [ 1 , 2 ] and is not in APX if p ∈ ( 2 , ∞ ) . In the case of an arbitrary norm, we propose an algorithm which finds an optimal solution in time O ( n d − 1 ( d + log ⁡ n ) ) , improving previously known algorithms. In particular, the two-dimensional problem can be solved in nearly linear time. We also present an improved algorithm for the cardinality-constrained version of the problem with running time O ( d n d + 1 ) . In the two-dimensional case, this version is shown to be solvable in nearly quadratic time.

We focus on fuzzy graphs with crisp vertex and fuzzy edge sets. A concept of the fuzzy chromatic number of these graphs based on fuzzy independent vertex set is used in this paper. A modified algorithm called a fuzzy chromatic algorithm is developed to find the fuzzy chromatic number of union of fuzzy graphs. Running time and complexity of the algorithm are also analyzed. Furthermore, we investigate some properties of the fuzzy chromatic number of union of fuzzy graphs. Finally, an application of the fuzzy chromatic number to determine the number of phases of an integrated traffic light system is proposed. We get different phases with different degrees of safety.

In the error compensation algorithm of the three-axis magnetic sensor, an M-estimation supplementary strategy is introduced to solve the problem that the abnormal sampling point will affect the results of geomagnetic data correction. M-estimation calculates the weight of each sampling point through the selected cost function, thereby reducing the influence of outliers. The Huber, Hampel and Tukey cost functions are selected to complete the error compensation algorithm of three-axis magnetic sensor based on M-estimation, and these three methods are compared in terms of mean square error, average error and running time through simulation. The simulation results show that the three methods are similar in the case of small deviation and small number of outliers. And the compensation effect based on the Tukey cost function is the best when the outliers are offset large and the number is large.

We study competitions structured as hierarchically shaped single-elimination tournaments. We define optimal tournaments by maximizing attractiveness such that the topmost players will have the chance to meet in higher stages of the tournament. We propose a dynamic programming algorithm for computing optimal tournaments and we provide its sound complexity analysis. Based on the idea of the dynamic programming approach, we also develop more efficient deterministic and stochastic sub-optimal algorithms. We present experimental results obtained with the Python implementation of all the proposed algorithms regarding the optimality of solutions and the efficiency of the running time.

This study presents a comparative evaluation of interval type-2 intuitionistic fuzzy logic system using three derivative-based learning algorithms on noisy regression problems. The motivation for this study is to manage uncertainty in noisy regression problems for the first time using both membership and non-membership functions that are fuzzy. The proposed models are able to handle ‘neither this nor that state’ in the noisy regression data with the aim of enabling hesitation and handling more uncertainty in the data. The gradient descent-backpropagation (first-order derivative), decoupled extended Kalman filter (second-order derivative) and hybrid approach (where the decoupled extended Kalman filter is used to learn the consequent parameters and gradient descent is used to optimise the antecedent parameters) are applied for the adaptation of the model parameters. The experiments are conducted using two artificially generated and one real-world datasets, namely Mackey–Glass time series, Lorenz time series and US stock datasets. Experimental analyses show that the extended Kalman filter-based learning approaches of interval type-2 intuitionistic fuzzy logic exhibit superior prediction accuracies to gradient descent approach especially at high noise level. The decoupled extended Kalman filter model however converges faster but incurs more computational overhead in terms of the running time.

Let $k\ge 1$ be an integer, and let $P= (f_1(x), \ldots, f_k(x) )$ be $k$ admissible linear polynomials over the integers, or \textit{the pattern}. We present two algorithms that find all integers $x$ where $\max{ \{f_i(x) \} } \le n$ and all the $f_i(x)$ are prime. Our first algorithm takes at most $O_P(n/(\log\log n)^k)$ arithmetic operations using $O(k\sqrt{n})$ space. Our second algorithm takes slightly more time, $O_P(n/(\log \log n)^{k-1})$ arithmetic operations, but uses only $n^{1/c}$ space for a constant $c>2$. We prove correctness unconditionally, but the running time relies on two unproven but reasonable conjectures. We are unaware of any previous complexity results for this problem beyond the use of a prime sieve. We also implemented several parallel versions of our second algorithm to show it is viable in practice. In particular, we found some new Cunningham chains of length 15, and we found all quadruplet primes up to $10^{17}$.

Highlights A series of strategies including feature concatenation, tweaks of ResNet50, and modification of the default anchors with the chaos optimization-based k -means algorithm were proposed to improve the detection performance of the original Faster R-CNN. The improved Faster R-CNN achieved an average precision of 97.71%, which is 5.98% higher than that of the original Faster R-CNN and 14.38% higher than that of YOLOv2. The improved Faster R-CNN greatly boosted the detection performance for potato buds without incurring any noticeable additional computational overhead. Abstract. This article proposes an improved Faster R-CNN model to achieve better detection performance for potato buds, with the goal of preparing for the automated cutting of seed potatoes. Detection results of Faster R-CNNs with eight pretrained networks were compared, and ResNet50 was adopted as the backbone network in Faster R-CNN. On this basis, three model strategies, including feature concatenation, tweaks of ResNet50, and modification of the default anchors with the chaos optimization-based k-means algorithm, were proposed to improve the detection performance for potato buds. Experimental results on the test set demonstrated that the improved Faster R-CNN achieved an average precision (AP) of 97.71%, which is 5.98% higher than that of the original Faster R-CNN and 14.38% higher than that of YOLOv2. In addition, the average running time per image with the improved Faster R-CNN was 0.166 s, the same as that of the original Faster R-CNN. In other words, the improved Faster R-CNN greatly boosted the detection performance for potato buds without incurring any noticeable additional computational overhead, thus satisfying the requirements for real-time processing. Consequently, the improved Faster R-CNN can provide a solid foundation for the automated cutting of seed potatoes. Keywords: Chaos optimization-based k-means, Default anchors, Faster R-CNN, Feature concatenation, Potato bud detection, Tweaks of ResNet50.

The instance reduction is one of the data preprocessing methods and aims to remove noises and (or) redundant instances from the training set. In the instance reduction, one of the most representative techniques is the edition method which can remove harmful instances from the training set to improve the prediction accuracy of k nearest neighbor (KNN). Nevertheless, most of existing edition methods still have some drawbacks, such as the parameter dependency, high computational time and relatively low accuracy. To solve these problems, we present a new fast parameter-free edition method based on local sets with natural neighbors (ELS). In ELS, we define a new concept of local sets by introducing natural neighbors. ELS can use the local sets to keep more reasonable class boundaries and effectively filtering out noisy instances (including global outliers). The main advantages of ELS are that (a) it is parameter-free; (b) it can remove global outliers and noisy instances; (c) it is relatively fast. Experiments clearly verify that (a) ELS outperforms existing representative edition methods in improving the prediction accuracy of KNN; (b) ELS can improve the performance of the condensation method and hybrid method in terms of both accuracy and reduction; (c) ELS consumes relatively low running time.

Previous real-time lane-level positioning algorithms for in-vehicle navigation systems have problems of inaccurate positioning and insufficient robustness. Therefore, this paper proposes a new lane-level positioning algorithm integrating Improved filter method, Curve Circle method and Improved Unet (ICCIU) method. Specifically, in ICCIU algorithm, we design improved filter method to improve the accuracy of original position by combining three filters to enhance image features, propose curve circle method to achieve real-time curve positioning by introducing two movement indicators to get precise curve position and design a light improved Unet method that integrates residual thought and cascading thought to detect the lane, and integrates two new parameters to get more accurate position by reducing the horizontal position errors The experiment results show that evaluation indicators of the improved Unet method are over 20% higher than those of the existing algorithms, the running time of single point positioning is about 28ms and lane-level accuracy is over 96% used by ICCIU, which demonstrates the pretty performance both in feasibility and efficiency of the new algorithm.

Predictive shift-reduce (PSR) parsing for hyperedge replacement (HR) grammars is very efficient, but restricted to a subclass of unambiguous HR grammars. To overcome this restriction, we have recently extended PSR parsing to generalized PSR (GPSR) parsing along the lines of Tomita-style generalized LR parsing. Unfortunately, GPSR parsers turned out to be too inefficient without manual tuning. This paper proposes to use memoization techniques to speed up GPSR parsers without any need of manual tuning, and which has been realized within the graph parser distiller Grappa. We present running time measurements for some example languages; they show a significant speed up by some orders of magnitude when parsing valid graphs. But memoization techniques do not help when parsing invalid graphs or if all parses of an ambiguous input graph shall be determined., In Proceedings GCM 2019, arXiv:1912.08966

We investigate the problem of computing the number of linear extensions of a givenn-element poset whose cover graph has treewidtht. We present an algorithm that runs in time$${\tilde{O}}(n^{t+3})$$O~(nt+3)for any constantt; the notation$${\tilde{O}}$$O~hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parametersnandtalone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.

In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (FPT) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O*(2pw2/4+o(pw2)) with respect to the pathwidth pw. We then develop faster FPT algorithms to count acyclic and totally acyclic orientations, running in O*(2bw2/2+o(bw2)) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.

Given n vectors x 0 , x 1 , … , x n − 1 in { 0 , 1 } m , how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the Closest Pair Problem. If these vectors are generated uniformly at random except two of them are correlated with Pearson-correlation coefficient ρ, then the problem is called the Light Bulb Problem. In this work, we propose a novel coding-based scheme for the Closest Pair Problem. We design both randomized and deterministic algorithms, which achieve the best-known running time when the length of input vectors m is small and the minimum distance is very small compared to m. Specifically, the running time of our randomized algorithm is O ( n log 2 ⁡ n ⋅ 2 c m ⋅ poly ( m ) ) and the running time of our deterministic algorithm is O ( n log ⁡ n ⋅ 2 c ′ m ⋅ poly ( m ) ) , where c and c ′ are constants depending only on the (relative) distance of the closest pair. When applied to the Light Bulb Problem, our result yields state-of-the-art deterministic running time when the Pearson-correlation coefficient ρ is very large. Specifically, when ρ ≥ 0.9933 , our deterministic algorithm runs faster than the previously best deterministic algorithm (Alman, SOSA 2019).

We revisit the problem of scheduling or assigning jobs non-preemptively so as to minimize the total completion time on m identical machines and on m uniformly related machines. This problem is polynomially solvable if all jobs are presented at once, even for unrelated machines. An online algorithm receives jobs one by one, such that every job is scheduled before the next job is presented. A robust algorithm with migration factor γ > 0 also receives jobs one at a time to be assigned immediately, but when a job of size p arrives, the algorithm can re-assign a subset of jobs of total size γ ⋅ p . That is, it can remove the jobs of one such subset from their positions and schedule them again in an arbitrary way. The goal is to obtain optimal or almost optimal solutions. We use the term schedule for a solution where every job is scheduled to a time slot on a machine, and the term assignment is used for a solution where a job is assigned to a machine and an optimal ordering of jobs (by SPT) is always used for every machine. We show that a nearly optimal schedule cannot be obtained for m ≥ 1 machines for any constant migration factor. For the variant of creating assignments, for one machine already the online problem is trivial, and we prove that an optimal assignment cannot be obtained for any constant migration factor γ for any m ≥ 2 and identical machines. Then, we deal with the problem of finding almost optimal assignments. We provide a fully polynomial time approximation scheme (FPTAS) for identical machines with constant migration factor, show how its running time can be reduced, and extend our result to the case of uniformly related machines. Our approximation schemes work even for the case where job departures may occur.

Radio frequency identification (RFID) systems, as one of the key components in the Internet of Things (IoT), have attracted much attention in the domains of industry and academia. In practice, the performance of RFID systems rather relies on the effectiveness and efficiency of anti-collision algorithms. A large body of studies have recently focused on the anti-collision algorithms, such as the Q-algorithm ( QA ), which has been successfully utilized in EPCglobal Class-1 Generation-2 protocol. However, the performance of those anti-collision algorithms needs to be further improved. Observe that fully exploiting the pre-processing time can improve the efficiency of the QA algorithm. With an objective of improving the performance for anti-collision, we propose a Nested Q-algorithm ( NQA ), which makes full use of such pre-processing time and incorporates the advantages of both Binary Tree ( BT ) algorithm and QA algorithm. Specifically, based on the expected number of collision tags, the NQA algorithm can adaptively select either BT or QA to identify collision tags. Extensive simulation results validate the efficiency and effectiveness of our proposed NQA (i.e., less running time for processing the same number of active tags) when compared to the existing algorithms.

We study techniques for solving the MaxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an equivalent instance in which the CNF formula becomes a linear CNF formula. We then show how more efficient branching strategies can be applied on linear CNF formulas. As applications, we present two algorithms: one of running time O ⁎ ( 1.194 k ) that solves the parameterized version of the problem, and the other of running time O ⁎ ( 1.237 n ) that solves the optimization version of the problem, both significantly improving previous best upper bounds.

Logical Methods in Computer Science ; Volume 17, Issue 1 ; 1860-5974, The notion of refinement plays an important role in software engineering. It is the basis of a stepwise development methodology in which the correctness of a system can be established by proving, or computing, that a system refines its specification. Wang et al. describe algorithms based on antichains for efficiently deciding trace refinement, stable failures refinement and failures-divergences refinement. We identify several issues pertaining to the soundness and performance in these algorithms and propose new, correct, antichain-based algorithms. Using a number of experiments we show that our algorithms outperform the original ones in terms of running time and memory usage. Furthermore, we show that additional run time improvements can be obtained by applying divergence-preserving branching bisimulation minimisation.

We propose simple algorithms for computing st-numberings and st-edge-numberings of graphs with running time O ( m ) . Unlike previous serial algorithms, these are not dependent on an initially chosen DFS-tree. Instead, we compute st-(edge-)numberings that are consistent with any open ear decomposition D of a graph in the sense that every ear of D is numbered increasingly or decreasingly. Recent applications need such st-numberings, and the only two linear-time algorithms that are known for this task use a complicated order data structure as black box. We avoid using this data structure by introducing a new and light-weight numbering scheme. In addition, we greatly simplify the recent algorithms for computing (the much less known) st-edge-numberings.

To solve the problem of DNN running too slowly on mobile terminals. The traditional approach is to use the edge server to cooperate with deep reasoning. However, this approach cannot be adapted to the partition according to the characteristics of each layer of the network and DNN, and can not achieve satisfactory reasoning acceleration effect. In this paper, an adaptive DNN partition algorithm is proposed to reduce the running time of DNN by considering the characteristics of each DNN layer and adaptively selecting the computing devices that should be divided and deployed in each layer. Experimental results show that the algorithm can effectively reduce the running time of DNN in different network environments and meet the delay requirements.

The longest common subsequence (LCS) problem on a pair of strings is a classical problem in string algorithms. Its extension, the semi-local LCS problem, provides a more detailed comparison of the input strings, without any increase in asymptotic running time. Several semi-local LCS algorithms have been proposed previously; however, to the best of our knowledge, none have yet been implemented. In this paper, we explore a new hybrid approach to the semi-local LCS problem. We also propose a novel bit-parallel LCS algorithm. In the experimental part of the paper, we present an implementation of several existing and new parallel LCS algorithms and evaluate their performance.

A rendezvous search aims to efficiently meet multiple searchers existing on different nodes on a network. The blind type of a rendezvous search is lightweight since it only uses a part of network information (adjacent information of each node), and is expected to use for various kinds of networks. As such a blind rendezvous search, we have proposed a random walk-based rendezvous search (RRS) that utilizes agents performing the random walks with the preferential selection of a high degree node. In our previous work, we have conducted the analysis and the experiment of an RRS to clarify its characteristics, under the simple circumstance where all agents start at the same time, and move every unit time by random walks with the same stochastic rule for selecting a next node from adjacent nodes. In this paper, as the first step to understand an RRS under the complex circumstances, we investigate the effect of agents’ diversities on the running time of an RRS through several experiments. As the result of experiments, we clarify the following things: (a) the running time of RRSes is almost the same when agents start random walks from different nodes at different times, (b) the difference of the stochastic rules to select a next node from adjacent nodes greatly affects the running time of an RRS, and (c) the difference of the frequencies of moving random walk agents greatly affects the running time of an RRS.

In this paper, an accuracy improvement of the quality-guided phase unwrapping algorithm is proposed. Our proposal is based on a modified phase derivative variance which provides more details on local variations especially for important patterns such as fringes and edges, hence distorted regions may be re-unwrapped according to this new reliable PDV. The proposed improvement is not only effective on accuracy but also on time, the obtained results have shown that the running time with our proposal is less than that of a skillful optimization-based algorithm. To prove effectiveness, the experimental test is carried out on simulated and real data, and the comparison is made under several relevant criteria.

In this paper, we propose a new low-complex preprocessing that enables conventional data sorting algorithms to be more efficient for medium and large data sets in a serial/parallel realization. First, we divide the main array into independent subarrays by a multi-level mean-based division. It is realized by calculating the mean value of each level as the pivot to divide its elements into two parts, greater and lower than the pivot, almost in the same lengths with a lower randomness rate to the main array. Then, subarrays can be sorted by the conventional sorting algorithms in a sequential serial realization to extract sorted data gradually or parallel realizations by using independent multi-core structures. It also holds the stability and adaptivity features of the sorting algorithm, if any. The effectiveness of the mean-based pivot to the random one is investigated. To show the superiority of the proposed idea, the simulation results are compared in view of the running time and the number of swaps required to the conventional and proposed serial and parallel Insertion-sort in different lengths of data. Finally, the complexity order of the proposed algorithm in serial and parallel implementations is compared to the conventional one.

The flow direction calculation over flat surfaces in a digital elevation model (DEM) is vital for hydrological analysis. The Garbrecht and Martz (G&M) algorithm is a widely used algorithm to obtain correct hydrological flow patterns over flat surfaces. In this study, we propose an efficient variant over the fastest variant of the G&M algorithm. The proposed variant introduces three improvements and significantly reduces redundant computation. For all tested DEMs, the running time of our proposed variant is 26% to 49% shorter than that of the fastest variant. The proposed variant can be used to obtain correct hydrological flow patterns over flat surfaces with less time.

In this paper, we propose a novel blended algorithm that has the advantages of the trisection method and the false position method. Numerical results indicate that the proposed algorithm outperforms the secant, the trisection, the Newton–Raphson, the bisection and the regula falsi methods, as well as the hybrid of the last two methods proposed by Sabharwal, with regard to the number of iterations and the average running time.

Single cell RNA Sequencing (scRNA-seq) measures gene expressions at the single cell level, and has been widely applied in biological and medical research. An important step in scRNA-seq data analysis is to use an unsupervised clustering algorithm to partition cells into different clusters based on the similarity of their gene expression profiles, followed by assigning cell type labels to each cluster. Recent advances in scRNA-seq technologies lead to a sharp increase of data size, posing a computational challenge to commonly used clustering algorithms that are memory-demanding or computation-intensive. Here, we propose a modified PQk-means algorithm that can greatly reduce both running time and memory usage while providing similar or better partition accuracy when it was tested on real scRNA-seq datasets.

Research on fractal networks is a dynamically growing field of network science. A central issue is to analyze fractality with the so-called box-covering method. As this problem is known to be NP-hard, a plethora of approximating algorithms have been proposed throughout the years. This study aims to establish a unified framework for comparing approximating box-covering algorithms by collecting, implementing, and evaluating these methods in various aspects including running time and approximation ability. This work might also serve as a reference for both researchers and practitioners, allowing fast selection from a rich collection of box-covering algorithms with a publicly available codebase., The paper has been published in Applied Network Science: https://appliednetsci.springeropen.com/articles/10.1007/s41109-021-00410-6

Given a set P of n points and a set S of m weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of P. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line L (while points of P can be anywhere in the plane). We present an \(O((m+n)\log (m+n)+\kappa \log m)\) time algorithm for the problem, where \(\kappa \) is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to \(O((n+m)\log (m+n))\). In addition, we solve in \(O((m+n)\log (m+n))\) time the \(L_{\infty }\) and \(L_1\) cases of the problem, in which the disks are squares and diamonds, respectively. Using our techniques, we further solve two other geometric coverage problems. Given in the plane a set P of n points and a set S of n weighted half-planes, we solve in \(O(n^4\log n)\) time the problem of finding a subset of half-planes to cover P so that their total weight is minimized. This improves the previous best algorithm of \(O(n^5)\) time by almost a linear factor. If all half-planes are lower ones, our algorithm runs in \(O(n^2\log n)\) time, which improves the previous best algorithm of \(O(n^4)\) time by almost a quadratic factor.

Batch normalization is currently the most widely used variant of internal normalization for deep neural networks. Additional work has shown that the normalization of weights and additional conditioning as well as the normalization of gradients further improve the generalization. In this work, we combine several of these methods and thereby increase the generalization of the networks. The advantage of the newer methods compared to the batch normalization is not only increased generalization, but also that these methods only have to be applied during training and, therefore, do not influence the running time during use. https://atreus.informatik.uni-tuebingen.de/seafile/d/8e2ab8c3fdd444e1a135/?p=%2FWeightAndGradientCentralization&mode=list.

7th Cologne–Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019, Enschede, Netherlands, 1 Jul 2019 - 3 Jul 2019 2nd Workshop on Enumeration Problems and Applications, WEPA 2018, Pisa, Italy, 5 Nov 2018 - 8 Nov 2018; Discrete applied mathematics 303, 94-107 (2021). doi:10.1016/j.dam.2020.08.012 special issue: "Combined Special Issue: 1) 17th Cologne–Twente Workshop on Graphs and Combinatorial Optimization (CTW 2019) / Guest edited by Johann Hurink, Bodo Manthey 2) WEPA 2018 (Second Workshop on Enumeration Problems and Applications); Guest edited by Takeaki Uno, Andrea Marino", Published by Elsevier, [S.l.]

Power iteration has been applied to compute the eigenvectors of the similarity matrix in spectral clustering tasks. However, these power iteration based clustering methods usually suffer from the following two problems: (1) the power iteration usually converges very slowly; (2) the singular value decomposition method adopted to obtain the eigenvectors of the similarity matrix is time-consuming. To solve these problems, we propose a novel clustering method named Adaptive Power Iteration Clustering (AdaPIC). Specifically, AdaPIC employs a sequence of rank-one matrices to approximate the normalized similarity matrix. Then, the first K+1 eigenvectors can be computed in parallel, and the stopping condition of power iteration can be automatically yielded based on the target clustering error. We performed extensive experiments on public datasets to demonstrate the effectiveness of the proposed AdaPIC method, comparing with leading baseline methods. The experimental results indicate that the proposed AdaPIC algorithm has a competitive advantage in running time. The running time taken by spectral clustering baseline methods is usually more than 2.52 times of that taken by AdaPIC. For clustering accuracy, AdaPIC outperforms classic PIC by 97% on average, over all experimental datasets. Moreover, AdaPIC achieves comparable clustering accuracy with other 3 baseline methods, and achieves 6%–15% better clustering accuracy than the remaining 6 state-of-the-art baseline methods. AI Singapore National Research Foundation (NRF) Submitted/Accepted version This research is supported, in part, by National Natural Science Foun- dation of China (61976030), Chongqing Municipal Education Commission- funded projects (KJ130709), and Supply Chain System CTBU Open Fund Project(1456025). This research is also supported, in part, by the National Research Foundation, Prime Minister’s Office, Singapore under its AI Singa- pore Programme (AISG Award No: AISG-GC-2019-003) and under its NRF Investigatorship Programme (NRFI Award No. NRF-NRFI05-2019-0002).

With the rapid development of the Internet, the complex network data presents an explosive growth. However, most of the complex networks in the real world are dynamic, How to effectively detect communities in dynamic complex networks has become a hot issue in current research. Therefore, we propose a dynamic network oriented multi-label propagation algorithm. Firstly, in order to reduce the running time, the SLPA algorithm of multi-label propagation class is selected as the basic algorithm; secondly, the SLPA algorithm is improved by using the history label to initialize the labels, and then the DSLPA (Speaker-listener Label Propagation Algorithm for Dynamic network) algorithm is designed and implemented. The experimental results showed that the proposed algorithm has high modularity and greatly reduces the running time.