The traveling-salesman problem, though in general NP-hard, possesses several special cases that can be solved in polynomial time. In particular, when the cost array C associated with an n-vertex traveling-salesman pro...
详细信息
The traveling-salesman problem, though in general NP-hard, possesses several special cases that can be solved in polynomial time. In particular, when the cost array C associated with an n-vertex traveling-salesman problem satisfies what are known as the Demidenko conditions, then a minimum-cost traveling-salesman tour can be computed in O(n2) time using a simple dynamic-programming algorithm. In this paper, we identify a subset-LAMBDA of the set of all cost arrays satisfying the Demidenko conditions, such that for any C is-an-element-of LAMBDA, the running time of the aforementioned dynamic-programming algorithm can be reduced to O(n). We obtain this speedup using recently developed techniques for on-line searching in Monge arrays.
Single character searching (SCS) methods have wide application in text processing, since many text processing algorithms need to search for a single character in a text string. An analysis compares 3 SCS methods. Tw...
详细信息
Single character searching (SCS) methods have wide application in text processing, since many text processing algorithms need to search for a single character in a text string. An analysis compares 3 SCS methods. Two of the methods are applied to the shift-or pattern-matching algorithm, and the performance of the different versions of the algorithm are compared. The shift-or pattern-matching algorithm has been extended to allow approximate pattern-matching and longest substring searching. The shift-or implementations are compared to the Tuned Boyer-Moore TBM) implementation. The Boyer-Moore pattern-matching algorithm is believed to have the fastest average case running time for ASCII applications. Although the shift-or implementations are getting closer to the efficiency of the Boyer-Moore algorithm, further improvement is needed to equal or better its performance.
Feature selection is frequently used to reduce the number of features in many applications where data of high dimensionality are involved. Lots of the feature selection methods mainly focus on measuring the correlatio...
详细信息
Feature selection is frequently used to reduce the number of features in many applications where data of high dimensionality are involved. Lots of the feature selection methods mainly focus on measuring the correlation (or similarity) between two features. However, most correlation measures are limited to handling only certain types of data. Feature space consisting of continuous/discrete feature or their combination presents a severe challenge to feature selection in terms of efficiency and effectiveness. This paper introduces a novel approach that can measure the correlation between a continuous and a discrete feature, and then proposes an efficient filter feature selection algorithm based on correlation analysis by removing weakly relevant and irrelevant features, as well as relevant but redundant features. Both theoretical and experimental comparisons with other representative filter approaches on UCI datasets show that the proposed algorithm is effective for selecting continuous and discrete features, as well as the mixture of continuous and discrete features. The performance of ECMBF is superior to other approaches in terms of dimensionality reduction and classification error rate. (C) 2015 Elsevier B.V. All rights reserved.
In this paper, we look at the time complexity of two agreement problems in networks of oblivious mobile robots, namely, at the gathering and scattering problems. Given a set of robots with arbitrary initial locations ...
详细信息
In this paper, we look at the time complexity of two agreement problems in networks of oblivious mobile robots, namely, at the gathering and scattering problems. Given a set of robots with arbitrary initial locations and no initial agreement on a global coordinate system, gathering requires that all robots reach the exact same but not predetermined location. In contrast, scattering requires that no two robots share the same location. These two abstractions are fundamental coordination problems in cooperative mobile robotics. Oblivious solutions are appealing for self-stabilization since they are self-stabilizing at no extra cost. As neither gathering nor scattering can be solved deterministically under arbitrary schedulers, probabilistic solutions have been proposed recently. The contribution of this paper is twofold. First, we propose a detailed time complexity analysis of a modified probabilistic gathering algorithm. Using Markov chains tools and additional assumptions on the environment, we prove that the convergence time of gathering can be reduced from O(n(2)) (the best known bound) to O(1) or O(log n . log(logn)), depending on the model of multiplicity detection. Second, using the same technique, we prove that scattering can also be achieved in fault-free systems with the same bounds. (C) 2010 Elsevier B.V. All rights reserved.
The combinatorial explosion of motif patterns occurring in ID and 2D arrays leads to the consideration of special classes of motifs growing linearly with the size of the input array. Such motifs, called irredundant mo...
详细信息
The combinatorial explosion of motif patterns occurring in ID and 2D arrays leads to the consideration of special classes of motifs growing linearly with the size of the input array. Such motifs, called irredundant motifs, are able to succinctly represent all of the other motifs occurring in the same array within reasonable time and space bounds. In previous work irredundant motifs were extracted from 2D arrays in O(N-2 log(2) nlog logn) and O(N-3) time, where N is the size of the 2D input array and n is its largest dimension. In this paper, we present an algorithm to extract irredundant motifs from 2D arrays that is quadratic in the size of the input. The input is defined on a binary alphabet. It is shown that the algorithm is optimal and practically faster than the previous ones. (C) 2009 Elsevier B.V. All rights reserved.
Given a digraph G = (V, E) and a cost function C: E --> R, which does not imply negative cost cycles, let us denote by G(delta) the graph obtained from G by adding to the cost of each edge the positive constant-del...
详细信息
Given a digraph G = (V, E) and a cost function C: E --> R, which does not imply negative cost cycles, let us denote by G(delta) the graph obtained from G by adding to the cost of each edge the positive constant-delta;then we want to compute the cost of the least cost path from a given origin r to each node v in the graph G(delta) for different choices of delta greater-than-or-equal-to 0, without having to run a least cost path algorithm everytime with a new cost function. Through a preprocessing of the given digraph based on the Bellmann-Ford algorithm, we will be able to obtain in time O(lambda(\E\ + \V\)) the necessary information to generate a structure that will allow us to answer each query in time O(log-lambda), where lambda is defined to be the length of the longest least cost path in the digraph. In particular, we will see that the only possible candidates to become least cost paths in a graph G(delta) are the least cost paths of bounded length in the original graph G;further, we will show that finding which of these candidates will become least cost path in a G(delta) and for which delta is equivalent to finding the lower envelope of at most lambda-lines, which, in turn, can be reduced to the lower convex hull problem for a set of ordered points.
Circular-arc graphs are rich in combinatorial structures. Various characterization and optimization problems on circular-arc graphs have been studied. In this paper, we present an extremely simple O(n) algorithm which...
详细信息
Circular-arc graphs are rich in combinatorial structures. Various characterization and optimization problems on circular-arc graphs have been studied. In this paper, we present an extremely simple O(n) algorithm which simultaneously solves the following three problems (the unweighted version) on circular-arc graphs: the maximum independent set, the minimum clique cover, and the minimum dominating set problems;whereas the best previous bounds for the latter two problems were O(n2) and O(n3), respectively. Our approach takes advantage of the underlying structure of circular-arc graphs that is amenable to greedy algorithms.
Heuristic search strategies have useful applications for problem solving in AI. It has been observed that bidirectional heuristic search algorithms can be potentially more efficient than their unidirectional counterpa...
详细信息
Heuristic search strategies have useful applications for problem solving in AI. It has been observed that bidirectional heuristic search algorithms can be potentially more efficient than their unidirectional counterparts. However, the problem with bidirectional search in practice is to make the two search fronts (forward and backward) meet in the middle. De Champeaux suggested a front-to-front algorithm [3] that overcomes this problem. But the disadvantage of that algorithm is that it is computationally very expensive. In this paper, we suggest a new front-to-front algorithm that is computationally much less expensive. Our algorithm does not guarantee optimality always, but its solution quality and execution time can be controlled by some external parameters. Finally, we present some experimental results on a generic state space problem, viz. 15-puzzle, showing the effectiveness of our algorithm.
The purpose of this note is to propose a complexity framework for the analysis of high multiplicity scheduling problems. Part of this framework relies on earlier work aiming at the definition of output-sensitive compl...
详细信息
The purpose of this note is to propose a complexity framework for the analysis of high multiplicity scheduling problems. Part of this framework relies on earlier work aiming at the definition of output-sensitive complexity measures for the analysis of algorithms which produce "large" outputs. However, different classes emerge according as we look at schedules as sets of starting times, or as related single-valued mappings.
暂无评论