Search

The article announces the selection of the study "Decomposition Algorithms for Stochastic Programming on a Computational Grid," written by Jeff Linderoth and Stephen Wright by the editorial board of the periodical "Computational Optimization and Applications," for the Best Paper Award 2004. The paper describes research carried out by the authors at the Argonne National Laboratory which was supported by the National Science Foundation (NSF). The research involved the development of middleware software, the discovery of new algorithms that could exploit the power of grid platforms while not being affected too seriously by its less felicitous features and the implementation of these algorithms using the resulting codes to solve touchstone problems in optimization.

Abstract Current implicit blending techniques are mostly designed for use in surface modelling, where only boundaries of the object defined by the implicit primitives are important. In contrast, in volumetric implicit modelling the interior of the object is also significant, which requires different and more suitable techniques for combining implicit primitives. In this paper, we first discuss irregularities that occur using the current techniques. Then, a new technique for blending implicit primitives, especially appropriate in volumetric modelling (e.g., cloud modelling), is introduced. It overcomes these abnormalities and gives us better results than current techniques. [ABSTRACT FROM AUTHOR]

In this paper, we establish some necessary and sufficient conditions for the solvability to a system of two-sided Sylvester-like tensor equations over the quaternion algebra. We also construct an expression of the general solution to the system when it is solvable. As an application, we give some solvability conditions and expressions of the η -Hermitian solutions to some systems of two-sided Sylvester-like quaternion tensor equations. We also provide some algorithms and numerical examples to illustrate the main results of this paper. [ABSTRACT FROM AUTHOR]

In this paper we provide an account of the Todd–Coxeter algorithm for computing congruences on semigroups and monoids. We also give a novel description of an analogue for semigroups of the so-called Felsch strategy from the Todd–Coxeter algorithm for groups. [ABSTRACT FROM AUTHOR]

During a conventional multiple-point statistics simulation, the algorithm may not find a matched neighborhood in the training image for some unsimulated pixels. These pixels are referred to as the dead-end pixels; the existence of the dead-end pixels means that multiple-point statistics simulation is not a simple sequential simulation. In this paper, the multiple-point statistics simulation is cast as a combinatorial optimization problem, and the efficient backtracking algorithm is developed to solve this optimization problem. The efficient backtracking consists of backtracking, forward checking, and conflict-directed backjumping algorithms that are introduced and discussed in this paper. This algorithm is applied to simulate multiple-point statistics properties of some synthetic training images; the results show that no anomalies occurred in any of the produced realizations as opposed to previously published methods for solving the dead-end pixels. In particular, in simulating a channel system, all the channels generated by this method are continuous, which is of paramount importance in fluid flow simulation applications. The results also show that the presence of hard data does not degrade the quality of the generated realizations. The presented method provides a robust algorithmic framework for performing MPS simulation. [ABSTRACT FROM AUTHOR]

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f:Z+n→R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1-1/e-ϵ)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/e-ϵ)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. [ABSTRACT FROM AUTHOR]

Problems are often too complex to solve them in an optimal way. The complexity arises from connections between their elements, such that a change in one element influences the performance of other elements. Kauffman’s NK model offers a way to depict such interdependencies and has therefore often been used in economic investigations of the influence of problem or search decomposition on the attainable results. However, papers on the effect of different decompositions on solution quality come to contradictory conclusions. Some observe an initial advantage of over-modularization where others do not. As they also differ in the employed search procedures, but do not base them on empirical findings, the present paper examines the results of more empirically based search strategies. Using algorithms based on innovation strategies derived from patent data, the paper establishes a clear advantage of correct problem decompositions. [ABSTRACT FROM AUTHOR]

This paper starts a series of publications devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices. The paper considers rank factorizations and, in particular, the relatively irreducible and ΔW-2 factorizations, which are used in solving spectral problems for two-parameter polynomial matrices F(λ, µ). Algorithms for computing these factorizations are suggested and applied to computing points of the regular, singular, and regular-singular spectra and the corresponding spectral vectors of F(λ, µ). The computation of spectrum points reduces to solving algebraic equations in one variable. A new method for computing spectral vectors for given spectrum points is suggested. Algorithms for computing critical points and for constructing a relatively free basis of the right null-space of F(λ, µ) are presented. Conditions sufficient for the existence of a free basis are established, and algorithms for checking them are provided. An algorithm for computing the zero-dimensional solutions of a system of nonlinear algebraic equations in two variables is presented. The spectral properties of the ΔW-2 method are studied. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

The chosen-message method is used to be employed in conducting Simple Power Analysis (SPA) attack by means of selecting special input messages. However, it is difficult to make distinction by visual observation i.e., SPA in practical IoT hardware environment. In this paper, we proposed a practical chosen-message correlation power analysis (CPA) attack which combines the chosen-message method with CPA for side channel attack. Then, we adopt other two practical chosen-messages, 1 and n + 1, to attack Boscher's right-to-left binary exponentiation algorithm which is wildly considered as an efficient side channel resistant algorithm. Finally, this paper presents a countermeasure to resist the chosen-message CPA attack over Boscher's algorithm without nullifying its countermeasure features to Differential Power Analysis (DPA) and Differential Fault Analysis (DFA). To validate the proposed attack method and countermeasure, a 1024-bit RSA coprocessor is constructed on the Xilinx Virtex-5 with the Side-channel Attack Standard Evaluation Board (SASEBO) to implement Boscher's algorithm as well as our proposed algorithm and launched the proposed attack on it separately. The experiment results show that the proposed attack and countermeasure are feasible and efficient. [ABSTRACT FROM AUTHOR]

In a paper published in 2013, Wang and Ma proposed a structure-preserving algorithm for computing the quaternion LU decomposition. They claimed that it was faster than the LU decomposition implemented in the quaternion Toolbox for Matlab (QTFM). But in 2015, Sangwine, one of the authors of QTFM, pointed out that the tests carried out by him did not support Wang and Ma's claim. We studied the structure-preserving algorithm of Wang and Ma, and found that the computations were based on element to element operations. In this paper, we re-propose real structure-preserving methods for the quaternion LU decomposition and partial pivoting quaternion LU decomposition, which make full use of high-level operations, and relation of operations between quaternion matrices and their real representation matrices. These algorithms are more efficient than that in QTFM using quaternion arithmetics. Numerical experiments are provided to demonstrate the efficiency of the real structure-preserving method. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm for solving the Cauchy problem for a two-dimensional difference equation with constant coefficients at a point, based on its coefficients and the initial data for the Cauchy problem, which are defined in a "strip." For this purpose, computer algebra methods are employed. To automate the process of computing the solution, the algorithm is implemented in MATLAB, with the input data being the matrix of coefficients of the two-dimensional polynomial difference equation, the coordinates of the initial data matrix (which defines the structure of the difference equation), and the coordinates of the point that determines the dimension of the initial data matrix. The output of the algorithm is a solution of the Cauchy problem (with the initial data defined in a "strip") for the two-dimensional difference equation, which is a function value at the desired point. [ABSTRACT FROM AUTHOR]

The primary goal of the secure socket layer protocol (SSL) is to provide confidentiality and data integrity between two communicating entities. Since the most computationally expensive step in the SSL handshake protocol is the server's RSA decryption, it is introduced that the proposed secret exchange algorithm can be used to speed up the SSL session initialization. This paper first points out that the previous batch method is impractical since it requires multiple certificates. It then proposes a unique certificate scheme to overcome the problem. The optimization strategy, which is based on the constrained model considering the user requirements-aware security ranking, focuses on the optimal result in different public key sizes. It is also introduced that the parameter is optimized when integrating user requirements for Internet QoS, such as the stability of the system and the tolerable response time. Finally, the proposed algorithm is evaluated to be practical and efficient through both analysis and simulation studies. [ABSTRACT FROM AUTHOR]

In the paper, the non-separability relation for finite state machines with time-outs is studied. A specific feature of such machines is integer-valued delays, or time-outs, which determine how long the finite state machine will stay in one or another state if there are no input actions. If the time-out is over and no input symbol has been applied, then the TFSM state is changed according to the transition under time delay. In the paper, an algorithm for constructing a separating sequence for such finite state machines is presented. Here, the separating sequence is a timed input sequence for which sets of input sequences of the TFSM do not intersect; hence, it is sufficient to apply the separating sequence once in order to distinguish the TFSMs by their output reactions. This algorithm underlies the algorithm for construction of test suites with respect to non-separability relation in the case where the fault domain is specified by means of a mutation machine. Test suite derivation with respect to non-separability relation by way of 'TFSM to FSM' transformation is discussed. [ABSTRACT FROM AUTHOR]

Bayesian uncertainty quantification of reservoir prediction is a significant area of ongoing research, with the major effort focussed on estimating the likelihood. However, the prior definition, which is equally as important in the Bayesian context and is related to the uncertainty in reservoir model description, has received less attention. This paper discusses methods for incorporating the prior definition into assisted history-matching workflows and demonstrates the impact of non-geologically plausible prior definitions on the posterior inference. This is the first of two papers to deal with the importance of an appropriate prior definition of the model parameter space, and it covers the key issue in updating the geological model—how to preserve geological realism in models that are produced by a geostatistical algorithm rather than manually by a geologist. To preserve realism, geologically consistent priors need to be included in the history-matching workflows, therefore the technical challenge lies in defining the space of all possibilities according to the current state of knowledge. This paper describes several workflows for Bayesian uncertainty quantification that build realistic prior descriptions of geological parameters for history matching using support vector regression and support vector classification. In the examples presented, it is used to build a prior description of channel dimensions, which is then used to history-match the parameters of both fluvial and deep-water reservoir geostatistical models. This paper also demonstrates how to handle modelling approaches where geological parameters and geostatistical reservoir model parameters are not the same, such as measured channel dimensions versus affinity parameter ranges of a multi-point statistics model. This can be solved using a multilayer perceptron technique to move from one parameter space to another and maintain realism. The overall workflow was implemented on three case studies, which refer to different depositional environments and geological modelling techniques, and demonstrated the ability to reduce the volume of parameter space, thereby increasing the history-matching efficiency and robustness of the quantified uncertainty. [ABSTRACT FROM AUTHOR]

In this paper, we attempt to introduce an algorithm which considers not only time factor but also cost, risk, and quality criteria to determine the critical path under fuzzy environment. In this algorithm first, decision makers allocate time, cost, risk, and quality to each activity. We are lacking in data and information, so in the proposed algorithm, the ratings of each activity and the weight of each criterion are described by fuzzy numbers and linguistic variables, which can be expressed in triangular fuzzy number. Linguistic variables are applied to represent the intensity of preferences of one criterion over another. Then, we add up triangular fuzzy numbers to determine the final evaluation value of each criterion for paths. Next, we use fuzzy TOPSIS, a technique for order preferences by similarity to an ideal solution, a method proposed by the authors in another paper, to choose the best alternative. Finally, numerical example is solved to illustrate the procedure of proposed method at the end of this paper. [ABSTRACT FROM AUTHOR]

In recent years, cases of newly emergent induced clusters have increased seismic hazard and risk in locations with social, environmental, and economic consequence. Thus, the need for a quantitative and robust means to discern induced seismicity has become a critical concern. This paper reviews a Matlab-based algorithm designed to quantify the statistical confidence between two time-series datasets. Similar to prior approaches, our method utilizes the cross-correlation to delineate the strength and lag of correlated signals. In addition, use of surrogate reshuffling tests allows for the dynamic testing against statistical confidence intervals of anticipated spurious correlations. We demonstrate the robust nature of our algorithm in a suite of synthetic tests to determine the limits of accurate signal detection in the presence of noise and sub-sampling. Overall, this routine has considerable merit in terms of delineating the strength of correlated signals, one of which includes the discernment of induced seismicity from natural. [ABSTRACT FROM AUTHOR]

Abstract  The study and research of evolutionary algorithms (EAs) is getting great attention in recent years. Although EAs have earned extensive acceptance through numerous successful applications in many fields, the problem of finding the best combination of evolutionary parameters especially for population size that need the manual settings by the user is still unresolved. In this paper, our system is focusing on differential evolution (DE) and its control parameters. To overcome the problem, two new systems were carried out for the self-adaptive population size to test two different methodologies (absolute encoding and relative encoding) in DE and compared their performances against the original DE. Fifty runs are conducted for every 20 well-known benchmark problems to test on every proposed algorithm in this paper to achieve the function optimization without explicit parameter tuning in DE. The empirical testing results showed that DE with self-adaptive population size using relative encoding performed well in terms of the average performance as well as stability compared to absolute encoding version as well as the original DE. [ABSTRACT FROM AUTHOR]

In this paper, the problem of reconstructing numerical derivatives from noisy data is considered. A new framework of mollification methods based on the L generalized solution regularization methods is proposed. A specific algorithm for the first three derivatives is presented in the paper, in which a modification of TSVD, termed cTSVD is chosen as the regularization technique. Numerical examples given in the paper verify the theoretical results and show efficiency of the new method. [ABSTRACT FROM AUTHOR]

Quantum Neural Network (QNN) is a young and outlying science built upon the combination of classical neural network and quantum computing. Making use of quantum linear superposition, this paper presents a quantum M-P neural network based on the analysis of the conventional M-P neural network. Moreover, the working principle of this proposed network and its corresponding weight updating algorithm are expatiated in the two cases of input state being in the orthogonal and non-orthogonal basic set, respectively. In addition, this paper not only validates that this quantum M-P network can realize some network functions, such as “XOR”, but also verifies the feasibility and validity of its weight learning algorithm by some simple examples. [ABSTRACT FROM AUTHOR]

Graphs are increasingly becoming a vital source of information within which a great deal of semantics is embedded. As the size of available graphs increases, our ability to arrive at the embedded semantics grows into a much more complicated task. One form of important hidden semantics is that which is embedded in the edges of directed graphs. Citation graphs serve as a good example in this context. This paper attempts to understand temporal aspects in publication trends through citation graphs, by identifying patterns in the subject matters of scientific publications using an efficient, vertical association rule mining model. Such patterns can (a) indicate subject-matter evolutionary history, (b) highlight subject-matter future extensions, and (c) give insights on the potential effects of current research on future research. We highlight our major differences with previous work in the areas of graph mining, citation mining, and Web-structure mining, propose an efficient vertical data representation model, introduce a new subjective interestingness measure for evaluating patterns with a special focus on those patterns that signify strong associations between properties of cited papers and citing papers, and present an efficient algorithm for the purpose of discovering rules of interest followed by a detailed experimental analysis. [ABSTRACT FROM AUTHOR]

This paper investigates the performance of synchronization algorithms on ccNUMA multiprocessors, from the perspectives of the architecture and the operating system. In contrast with previous related studies that emphasized the relative performance of synchronization algorithms, this paper takes a new approach by analyzing the sources of synchronization latency on ccNUMA architectures and how can this latency be reduced by leveraging hardware and software schemes in both dedicated and multiprogrammed execution environments. From the architectural perspective, the paper identifies the implications of directory-based cache coherence on the latency and scalability of synchronization instructions and examines if and how can simple hardware that accelerates these instructions be leveraged to reduce synchronization latency. From the operating system's perspective, the paper evaluates in a unified framework, user-level, kernel-level and hybrid algorithms for implementing scalable synchronization in multiprogrammed execution environments. Along with visiting the aforementioned issues, the paper contributes a new methodology for implementing fast synchronization algorithms on ccNUMA multiprocessors. The relevant experiments are conducted on the SGI Origin2000, a popular commercial ccNUMA multiprocessor. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new class of algebras satisfying certain conditions which has been named power algebras and we prove some fixed point theorems for a new class of contractions. We give new conditions for the existence and uniqueness of fixed points for this new class of mappings which are not a contraction in the usual algebra. Also, we introduce a new iterative algorithm for fixed-point problems in a Banach algebra. This results improve and extend the corresponding conclusions of the Ishikawa algorithm under weaker conditions and lead to stronger results. In conclusion, we give an application to nonlinear integral equations. [ABSTRACT FROM AUTHOR]

It has been pointed out by Jones D. R. that the DIRECT global optimization algorithm can quickly get close to the basin of the optimum but takes longer to achieve a high degree of accuracy. In this paper, we introduce a bilevel strategy into a modifed DIRECT algorithm to overcome this shortcoming. The proposed algorithm is proved to be convergent globally. Numerical results show that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS-ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS-ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Polycube construction and deformation are essential problems in computer graphics. In this paper, we present a robust, simple, efficient, and automatic algorithm to deform the meshes of arbitrary shapes into polycube form. We derive a clear relationship between a mesh and its corresponding polycube shape. Our algorithm is edge-preserving, and works on surface meshes with or without boundaries. Our algorithm outperforms previous ones with respect to speed, robustness, and efficiency. Our method is simple to implement. To demonstrate the robustness and effectivity of our method, we have applied it to hundreds of models of varying complexity and topology. We demonstrate that our method compares favorably to other state-of-the-art polycube deformation methods. [ABSTRACT FROM AUTHOR]

With the development of science and technology, the popularity of smart phones has made exponential growth in mobile phone application market. How to help users to select applications they prefer has become a hot topic in recommendation algorithm. As traditional recommendation algorithms are based on popularity and download, they inadvertently fail to recommend the desirable applications. At the same time, many users tend to pay more attention to permissions of those applications, because of some privacy and security reasons. There are few recommendation algorithms which take account of apps' permissions, functionalities and users' interests altogether. Some of them only consider permissions while neglecting the users' interests, others just perform linear combination of apps' permissions, functionalities and users' interests to implement top-N recommendation. In this paper, we devise a recommendation method based on both permissions and functionalities. After demonstrating the correlation of apps' permissions and users' interests, we design an app risk score calculating method ARSM based on app-permission bipartite graph model. Furthermore, we propose a novel matrix factorization algorithm MFPF based on users' interests, apps' permissions and functionalities to handle personalized app recommendation. We compare our work with some of the state-of-the-art recommendation algorithms, and the results indicate that our work can improve the recommendation accuracy remarkably. [ABSTRACT FROM AUTHOR]

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains three main contributions: (1) we present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with N servers that is resilient to f server failures, we show that the communication cost of CAS is $$\frac{N}{N-2f}$$ . The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with garbage collection (CASGC). The CASGC algorithm is parameterized by an integer $$\delta $$ and has a bounded storage cost. We show that the CASGC algorithm satisfies atomicity. In every execution of CASGC where the number of server failures is no bigger than f, we show that every write operation invoked at a non-failing client terminates. We also show that in an execution of CASGC with parameter $$\delta $$ where the number of server failures is no bigger than f, a read operation terminates provided that the number of write operations that are concurrent with the read is no bigger than $$\delta $$ . We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of $$\frac{N}{N-f}$$ measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC. [ABSTRACT FROM AUTHOR]

Due to the time-variant channel, outdated channel state information (CSI) largely reduce the performance of double codebook beamforming system. This paper studies the two codebooks independently and proposes an adaptive feedback period adjustment Strategy for long-term codebook and a prediction estimation algorithm for short-term codebook respectively. The former dynamically adjusts feedback period so as to improve the feedback timeliness and uplink feedback resource utilization. The later adopts improved Kalman prediction algorithm to predict CSI. Finally simulation results shows that the proposed schemes can effectively improve the performance of double codebook estimation with outdated CSI. [ABSTRACT FROM AUTHOR]

In this paper, we consider a linear mixed model with measurement errors in fixed effects. We find the corrected score function estimators for the variance components. An iterative algorithm is proposed for estimating the parameters. The computations on each iteration of this algorithm are those associated with computing estimates of fixed and random effects for given values of the variance components. We also derive the consistency of the estimators under regularity conditions. The simulation study shows that for relatively small sample size the corrected estimators perform very well. Finally, an example of real data is given for illustration. [ABSTRACT FROM AUTHOR]

In this paper we propose two iterative schemes for solving equilibrium problems which are called dual extragradient algorithms. In contrast with the primal extragradient methods in Quoc et al. (Optimization 57(6):749-776, ) which require to solve two general strongly convex programs at each iteration, the dual extragradient algorithms proposed in this paper only need to solve, at each iteration, one general strongly convex program, one projection problem and one subgradient calculation. Moreover, we provide the worst case complexity bounds of these algorithms, which have not been done in the primal extragradient methods yet. An application to Nash-Cournot equilibrium models of electricity markets is presented and implemented to examine the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Structured matrices are encountered in various guises in many mathematical models which describe problems of the real world. In fact, they are the algebraic translation of the specific properties at the basis of the physical problem. The analysis and the exploitation of matrix structures is the first fundamental step in the design of highly efficient algorithms for the solution of complex computational problems. [ABSTRACT FROM AUTHOR]

This paper deals with the hybrid flow shop scheduling problems in which there are sequence-dependent setup times, commonly known as the SDST hybrid flow shops. This paper describes a Greedy Randomized Adaptive Search Procedure (GRASP) version for scheduling of a SDST hybrid flow shop, in which each stage (work center) consists of parallel identical machines. In this problem, each job has a different release date and consists of ordered operations that have to be processed on machines from different centers in the same order. In addition, the processing times of the operations on some machine centers may vary between a minimum and a maximum value depending on the use of a continuously divisible resource. We consider a non-regular optimization criterion based on due dates which are not a priori given or fixed but can be assigned by a decision maker. A due-date assignment cost is included into the objective function. Finally, the results obtained using GRASP are analyzed in order to find the preferred parameter settings and the features of the algorithms that have a strong influence on the solution quality. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we examine the use of biased neighborhood structures for local search in multiobjective memetic algorithms. Under a biased neighborhood structure, each neighbor of the current solution has a different probability to be sampled in local search. In standard local search, all neighbors of the current solution usually have the same probability because they are randomly sampled. On the other hand, we assign larger probabilities to more promising neighbors in order to improve the search ability of multiobjective memetic algorithms. In this paper, we first explain our multiobjective memetic algorithm, which is a simple hybrid algorithm of NSGA-II and local search. Then we explain its variants with biased neighborhood structures for multiobjective 0/1 knapsack and flowshop scheduling problems. Finally we examine the performance of each variant through computational experiments. Experimental results show that the use of biased neighborhood structures clearly improves the performance of our multiobjective memetic algorithm. [ABSTRACT FROM AUTHOR]

Abstract  Applications of multi-objective genetic algorithms (MOGAs) in engineering optimization problems often require numerous function calls. One way to reduce the number of function calls is to use an approximation in lieu of function calls. An approximation involves two steps: design of experiments (DOE) and metamodeling. This paper presents a new approach where both DOE and metamodeling are integrated with a MOGA. In particular, the DOE method reduces the number of generations in a MOGA, while the metamodeling reduces the number of function calls in each generation. In the present approach, the DOE locates a subset of design points that is estimated to better sample the design space, while the metamodeling assists in estimating the fitness of design points. Several numerical and engineering examples are used to demonstrate the applicability of this new approach. The results from these examples show that the proposed improved approach requires significantly fewer function calls and obtains similar solutions compared to a conventional MOGA and a recently developed metamodeling-assisted MOGA. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of finding the generators of the solution space for a system of inequalities A ⊗ x ≥ x in max-plus algebra. It provides an improved algorithm which can be used to find a smaller set of generators for the solution space by skipping a large number of invalid generators. [ABSTRACT FROM AUTHOR]

Abstract  Two minimal requirements for a satisfactory multiagent learning algorithm are that it 1. learns to play optimally against stationary opponents and 2. converges to a Nash equilibrium in self-play. The previous algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action (repeated) games—assuming that the opponent’s mixed strategy is observable. Another algorithm, ReDVaLeR (which was introduced after the algorithm described in this paper), achieves the two properties in games with arbitrary numbers of actions and players, but still requires that the opponents' mixed strategies are observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have the two properties in games with arbitrary numbers of actions and players. It is still the only algorithm that does so while only relying on observing the other players' actual actions (not their mixed strategies). It also learns to play optimally against opponents that eventually become stationary. The basic idea behind AWESOME (Adapt When Everybody is Stationary, Otherwise Move to Equilibrium) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. We provide experimental results that suggest that AWESOME converges fast in practice. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing future multiagent learning algorithms as well. [ABSTRACT FROM AUTHOR]

Abstract??Scheduling algorithms are used in content delivery systems to control the resource allocation rate. They not only improve system efficiency, but also increase user satisfaction. Lower renege rate and less waiting time for users are the main goals for a scheduling algorithm. Among existing algorithms, On-Demand strategy does not perform well, while rate control channel allocation policies performs much better. Pure-Rate-Control (PRC) and Multiple-Service-Class (MSC) belong to the rate control algorithms. MSC performs well, but a drawback is that it uses the Hot Index, which is hard to decide and has significant effects on the performance. In order to solve this problem and to improve the overall system performance, two new algorithms, Modified MSC(MMSC) and Adaptive Algorithm (AA), are proposed in this paper. Both of them solved the problem of MSC very well and improved the overall performance. For example, the renege rate of AA is about 5.4% less than that of MMSC, and about 9.8% less than that of MSC. [ABSTRACT FROM AUTHOR]

Abstract Support vector machines (SVMs) are originally designed for binary classifications. As for multi-classifications, they are usually converted into binary ones. In the conventional multi-classifiable algorithms, One-against-One algorithm is a very power method. However, there exists a middle unclassifiable region. In order to overcome this drawback, a novel method called Nesting Algorithm is presented in this paper. Our ideas are as follows: firstly, construct the optimal hyperplanes based on One-against-One approach. Secondly, if there exist data points in the middle unclassifiable region, select them to construct the optimal hyperplanes with the same hyperparameters. Thirdly, repeat the second step until there are no data points in the unclassifiable region or the region is disappeared. In this paper, we also prove the validity of the proposed algorithm for unclassifiable region and give the computational complexity analysis of the method. In order to examine the training accuracy and the generalization performance of the proposed algorithm, One-against-One algorithm, fuzzy least square support vector machine (FLS-SVM) and the proposed algorithm are applied to five UCI datasets. The results show that the training accuracy of the proposed algorithm is higher than the others, and its generalization performance is also comparable with them. [ABSTRACT FROM AUTHOR]

Abstract  Case-based reasoning (CBR) is an effective and fast problem-solving methodology, which solves new problems by remembering and adaptation of past cases. With the increasing requests for useful references for all kinds of problems and from different locations, keeping a single CBR system seems to be outdated and not practical. Multi-CBR agents located in different places are of great support to fast meet these requests. In this paper, the architecture of a multi-CBR agent system is proposed, where the CBR agents locate at different places, and are assumed to have the same ability to deal with new problem independently. When the requests in a request queue from different places are coming one by one, we propose a new policy of dispatching which agent to satisfy the request queue. Throughout the paper, we assume that the system must solve the coming request by considering only past requests. In this context, the performance of traditional greedy algorithms is not satisfactory. We apply a new but simple approach – competitive algorithm for on-line problem (called On-line multi-CBR agent dispatching algorithm) to determine the dispatching policy to keep comparative low cost. The corresponding on-line dispatching algorithm is proposed and the competitive ratio is given. Based on the competitive algorithm, the dispatching of multi-CBR agents is optimized. [ABSTRACT FROM AUTHOR]

Business process redesign and improvement has become an increasingly attractive subject in the wider area of business process intelligence. Although there have been many attempts to establish a business process redesign framework, there is little work on the actual optimisation of business processes with given objectives. Furthermore, most of the attempts to optimise a business process are manual and do not involve a formal automated methodology. This paper proposes a process improvement approach for automated multi-objective optimisation of business processes. The proposed framework uses a generic business process model that is formally defined. The formal definition of business processes is necessary to ensure that the optimisation will take place in a clearly defined, repeatable and verifiable way. Multi-objectivity is expressed in terms of process cost and duration as two key objectives for any business process. The business process model is programmed and incorporated into a software optimisation platform where a selection of multi-objective optimisation algorithms can be applied to a business process design. This paper outlines a case study of business process design that is optimised by the state-of-the-art multi-objective optimisation algorithm NSGA2. The results indicate that, although business process optimisation is a highly constrained problem with fragmented search space, a number of alternative optimised business processes that meet the optimisation criteria can be produced. The paper also provides directions for future research in this area. [ABSTRACT FROM AUTHOR]

Symbolic model checkers use BDDs to represent arithmetic constraints over bounded integer variables. The size of such BDDs can in the worst case be exponential in the number and size (in bits) of the integer variables. In this paper we show how to construct linear-sized BDDs for linear integer arithmetic constraints. We present basic constructions for atomic equality and inequality constraints and generalize our complexity results for arbitrary linear arithmetic formulas. We also present three alternative ways of handling out-of-bounds transitions and discuss heterogeneous bounds on integer variables. We experimentally compare our approach to other BDD-based symbolic model checkers and demonstrate that the algorithms presented in this paper can be used to improve their performance significantly. [ABSTRACT FROM AUTHOR]

Because the orbital periods for planetary orbital transfers are of order hour, the primary objective of an optimal trajectory is to minimize the propellant consumption. In this paper, we present a systematic investigation of optimal trajectories for planetary orbital transfer. Major results on thrust control, propellant consumption, and flight time are presented with particular reference to LEO-to-GEO transfer. The following results were obtained with the sequential gradient-restoration algorithm in either single-subarc form or multiple-subarc form: (i) For minimum propellant consumption, the thrust direction is tangent to the flight path. The thrust magnitude has a three-subarc form: powered flight with maximum thrust is followed by coasting flight, which is followed by powered flight with maximum thrust. (ii) The flight time is determined mainly by the thrust-to-weight ratio. A transfer via chemical engines is relatively short: usually, it requires less than one cycle to achieve the mission, which involves a large portion of coasting flight. A transfer via electrical engines is relatively long: usually, it requires a multicycle spiral trajectory to achieve the mission, which involves a large portion of powered flight, mostly in the first subarc. (iii) The propellant consumption is determined mainly by the specific impulse: the electrical engine is more efficient than the chemical engine, resulting in lower propellant consumption and higher payload. [ABSTRACT FROM AUTHOR]

This paper provides an extension of the Dynamic Conditional Correlation model of Engle (2002) by allowing both the unconditional correlation and the parameters to be driven by an unobservable Markov chain. We provide the estimation algorithm and perform an empirical analysis of the contagion phenomenon in which our model is compared to the traditional CCC and DCC representations. [ABSTRACT FROM AUTHOR]

Abstract Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O(?d? + |d| log|d|) time and O(?d?) time respectively, where |d| and ?d? are measures of the change in the input and output. The paper also shows how to generalize the algorithm to various classes of multiple insertions/deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice. [ABSTRACT FROM AUTHOR]

Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This paper studies how to derive safe linear relaxations to account for numerical errors arising when computing the linear coefficients. It first proposes two classes of safe linear estimators for univariate functions. Class-1 estimators generalize previously suggested estimators from quadratic to arbitrary functions, while class-2 estimators are novel. When they apply, class-2 estimators are shown to be tighter theoretically (in a certain sense) and almost always tighter numerically. The paper then generalizes these results to multivariate functions. It shows how to derive estimators for multivariate functions by combining univariate estimators derived for each variable independently. Moreover, the combination of tight class-1 safe univariate estimators is shown to be a tight class-1 safe multivariate estimator. Finally, multivariate class-2 estimators are shown to be theoretically tighter (in a certain sense) than multivariate class-1 estimators. [ABSTRACT FROM AUTHOR]

In traditional distributed power control (DPC) algorithms, every user in the system is treated in the same way, i.e., the same power control algorithm is applied to every user in the system. In this paper, we divide the users into different groups depending on their channel conditions and use different DPC accordingly. Our motivation comes from the fact that different DPC algorithms have its own advantages and drawbacks, and our aim in this paper is to “combine” the advantages of different DPC algorithms, and we use soft computing techniques for that. In the simulations results, we choose Foschini and Miljanic Algorithm in [3], which has relatively fast convergence but is not robust against time-varying link gain changes and CIR estimation errors, and fixed step algorithm of Kim [3], which is robust but its convergence is slow. By “combining” these two algorithms using soft computing techniques, the resulting algorithm has fast convergence and is robust. [ABSTRACT FROM AUTHOR]

A new algorithm for ranking the input features and obtaining the best feature subset is developed and illustrated in this paper. The asymptotic formula for mutual information and the expectation maximisation (EM) algorithm are used to developing the feature selection algorithm in this paper. We not only consider the dependence between the features and the class, but also measure the dependence among the features. Even for noisy data, this algorithm still works well. An empirical study is carried out in order to compare the proposed algorithm with the current existing algorithms. The proposed algorithm is illustrated by application to a variety of problems. [ABSTRACT FROM AUTHOR]

In many scientific applications, dynamic data redistribution is used to enhance algorithm performance and achieve data locality in parallel programs on distributed memory multi-computers. In this paper, we present a new method, Compressed Diagonals Remapping (CDR) technique aims to the efficiency of runtime data redistribution on banded sparse matrices. The main idea of the proposed technique is first to compress the source matrix into a Compressed Diagonal Matrix (CDM) form. Based on the compressed diagonal matrix, a one-dimensional local and global index transformation method can be applied to carry out data redistribution on the compressed diagonal matrix. This process is identical to redistribute data in the two-dimensional banded sparse matrix. The CDR technique uses an efficient one-dimensional indexing scheme to perform data redistribution on banded sparse matrix. A significant improvement of this approach is that a processor does not need to determine the complicated sending or receiving data sets for dynamic data redistribution. The indexing cost is reduced significantly. The second advantage of the present techniques is the achievement of optimal packing/unpacking stages consequent upon the consecutive attribute of column elements in a compressed diagonal matrix. Another contribution of our methods is the ability to handle sparse matrix redistribution under two disjoint processor grids in the source and destination phases. A theoretical model to analyze the performance of the proposed technique is also presented in this paper. To evaluate the performance of our methods, we have implemented the present techniques on an IBM SP2 parallel machine along with the v2m algorithm and a dense redistribution strategy. The experimental results show that our technique provides significant improvement for runtime data redistribution of banded sparse matrices in most test samples. [ABSTRACT FROM AUTHOR]

abstract. in this paper, a multi-grid solver for the discretisation of partial differential equations on complicated domains will be developed. the algorithm requires as input only the given discretisation instead of a hierarchy of discretisations on coarser grids. such auxiliary grids and discretisations will be generated in a black-box fashion and will be employed to define purely algebraic intergrid transfer operators. the geometric interpretation of the algorithm allows one to use the framework of geometric multigrid methods to prove its convergence. the focus of this paper is on the formulation of the algorithm and the demonstration of its efficiency by numerical experiments while the analysis is carried out for some model problems. [ABSTRACT FROM AUTHOR]

This paper looks at a way to adaptively operate the cdma2000 reverse link (RL) using velocity estimation. A simple analysis of the power control process is carried out to better understand the impact of power control on the efficacy of the RL operation, both at the link and system levels. The structure and performance of the RL is presented, and different areas where the velocity estimation could be used are identified, e.g., turning off power control selectively, adjusting traffic-to-pilot ratios and controlling the transmit level of pilots for mobiles in dormant mode. The algorithm for doing the velocity estimation and its performance concludes the paper. [ABSTRACT FROM AUTHOR]