The input and output of an on-line computation involving redundant numbers must generally be compatible with standard nonredundant formats. When rounding of a result is required in the last computation step, the proce...
详细信息
ISBN:
(纸本)0780365143
The input and output of an on-line computation involving redundant numbers must generally be compatible with standard nonredundant formats. When rounding of a result is required in the last computation step, the process can be combined with on-the-fly conversion of the redundant output into nonredundant form and thus introduces no extra delay. However, if multiple on-line operations are to be performed before obtaining a final result, the preceding method would be inapplicable to the intermediate results. We present a solution scheme where rounding (subtraction of ulp, no action, addition of ulp) is represented by an additional digit attached to the number, thus obviating the need for modifying any of the previously produced digits. This added digit forms a second least-significant digit (LSD), leading to the designation "double-LSD numbers" for the resulting representation. We show that on-line arithmetic with double-LSD numbers is only slightly more complex than with ordinary signed-digit numbers.
This paper considers the problem of walking in the street with a mobile robot. The robot starts from a point s to search the target point t. The robot is equipped with a minimal sensing sensor that can only detect the...
详细信息
ISBN:
(纸本)9781467390262
This paper considers the problem of walking in the street with a mobile robot. The robot starts from a point s to search the target point t. The robot is equipped with a minimal sensing sensor that can only detect the discontinuities in depth information (or gaps), but has no prior knowledge of the street. The performance of our strategy is measured in terms of the competitive ratio, with respect to the length of the optimal path for walking in the street with complete knowledge. We propose a new 9-competitive strategy, and prove that it is optimal by showing a matching lower bound, whereas the previous best approach proposed by Tabatabaei et al. has a competitive ratio of 11.
Cleaning of young forest stands is a multicriteria problem with conflicting goals. This kind of forest management treatment is performed by human beings but it is possible that this work may be performed by artificial...
详细信息
ISBN:
(纸本)9789077381571
Cleaning of young forest stands is a multicriteria problem with conflicting goals. This kind of forest management treatment is performed by human beings but it is possible that this work may be performed by artificial agents in the future. The artificial agents need detailed information about how to clean a forest stand and/or what are the goals for cleaning. One problem in development of cleaning rules for artificial cleaning agents is that explicit knowledge about good cleaning results is not detailed. In this paper we present a tool for developing and testing rules and judging evaluation functions for cleaning. We illustrate this tool by presenting examples of some ways to clean forest stands in a computer environment and we present how the cleaning results can be evaluated. In order to obtain material for experiments it is also possible to simulate forest stands using this tool.
This paper proposes a fast method for on-line capacitor control in distribution systems. The proposed method makes use of a hybrid method of parallel tabu search (PTS) and ordinal optimization (OO) to determine the op...
详细信息
ISBN:
(纸本)0780379896
This paper proposes a fast method for on-line capacitor control in distribution systems. The proposed method makes use of a hybrid method of parallel tabu search (PTS) and ordinal optimization (OO) to determine the optimal combination of capacitor banks. OO is used to supplement the performance of PTS so that computational time is significantly reduced to carry out on-line capacitor control. PTS has a couple of strategies. One is the decomposition of the neighborhood of tabu search (TS) into subneighborhoods to speed up computational time. The other is to use multiple tabu lengths that make solution candidates diverse to obtain a better solution. The proposed method is successfully applied to a sample system. A comparison is made between the proposed and conventional methods in terms of computational time and solution accuracy.
In this paper, we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance-graph (which has n vertices) is revealed in t clusters, 2 <= t <= n. We firs...
详细信息
ISBN:
(纸本)3540309357
In this paper, we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance-graph (which has n vertices) is revealed in t clusters, 2 <= t <= n. We first focus on the on-line version of the following problem: finding a maximum-weighted subgraph satisfying some hereditary property. Then, we deal with the particular case of the independent set. For all these problems, we are interested in two types of results: the competitivity ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them.
In the on-line rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives over time. The decision maker needs to insert the new ...
详细信息
ISBN:
(纸本)9780769537290
In the on-line rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives over time. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. In this paper, we consider the online rescheduling problem to minimize makespan under a limit on the maximum sequence disruption constraints and give an onlinealgorithm of competitive ratio 3/2.
:We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
:We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
Bayesian models are generally computed with Markov Chain Monte Carlo (MCMC) methods. The main disadvantage of MCMC methods is the large number of iterations they need to sample the posterior distributions of model par...
详细信息
Bayesian models are generally computed with Markov Chain Monte Carlo (MCMC) methods. The main disadvantage of MCMC methods is the large number of iterations they need to sample the posterior distributions of model parameters, especially for large datasets. On the other hand, variable selection remains a challenging problem due to its combinatorial search space, where Bayesian models are a promising solution. In this work, we study how to accelerate Bayesian model computation for variable selection in linear regression. We propose a fast Gibbs sampler algorithm, a widely used MCMC method that incorporates several optimizations. We use a Zellner prior for the regression coefficients, an improper prior on variance, and a conjugate prior Gaussian distribution, which enable dataset summarization in one pass, thus exploiting an augmented set of sufficient statistics. Thereafter, the algorithm iterates in main memory. Sufficient statistics are indexed with a sparse binary vector to efficiently compute matrix projections based on selected variables. Discovered variable subsets probabilities, selecting and discarding each variable, are stored on a hash table for fast retrieval in future iterations. We study how to integrate our algorithm into a Database Management System (DBMS), exploiting aggregate User-Defined Functions for parallel data summarization and stored procedures to manipulate matrices with arrays. An experimental evaluation with real datasets evaluates accuracy and time performance, comparing our DBMS-based algorithm with the R package. Our algorithm is shown to produce accurate results, scale linearly on dataset size, and run orders of magnitude faster than the R package.
Automatic speech recognition (ASR) technologies enable humans to communicate with computers. Isolated word recognition (IWR) is an important part of many known ASR systems. Minimizing the word error rate in cases of i...
详细信息
Automatic speech recognition (ASR) technologies enable humans to communicate with computers. Isolated word recognition (IWR) is an important part of many known ASR systems. Minimizing the word error rate in cases of incremental learning is a unique challenge for developing an on-line ASR system. This paper focuses on on-line IWR using a recursive hidden Markov model (HMM) multivariate parameter estimation algorithm. The maximum likelihood method was used to estimate the unknown parameters of the model, and an algorithm for the adapted recursive EM algorithm for HMMs parameter estimation was derived. The resulting recursive EM algorithm is unique among its counterparts because of state transition probabilities calculation. It obtains more accurate parameter estimates compared to other algorithms of this type. In our experiment, the algorithm was implemented and adapted to several datasets for IWR. Thus, the recognition rate and algorithm convergence results are discussed in this work.
In this paper, we consider a semi-on-line scheduling problem of two identical machines with common maintenance time interval and nonresumable availability. We prove a lower bound of 2.79129 on the competitive ratio an...
详细信息
In this paper, we consider a semi-on-line scheduling problem of two identical machines with common maintenance time interval and nonresumable availability. We prove a lower bound of 2.79129 on the competitive ratio and give an on-line algorithm with competitive ratio 2.79633 for this problem.
暂无评论