Search

In edge computing, application components can be placed over a range of computational devices from cloud data centers to nodes at the network edge. Application placement can have significant impact on important metrics like latency and resource utilization. Thus, application placement is an important optimization problem. In edge computing, the characteristics of both the infrastructure and the application may change over time, which may require the dynamic re-optimization of the application placement. Most algorithms suggested so far for the dynamic re-optimization of edge application placement are centralized, i.e., they rely on one entity collecting information from the whole infrastructure and making decisions centrally. However, centralized approaches suffer from limited scalability and are vulnerable to failures. In this paper, we present a decentralized approach for the dynamic re-optimization of edge application placement. We adopt an algorithm of Malek et al. for distributed systems and modify it to make it applicable to edge computing. In this approach, each node makes decisions autonomously, using auctions for coordination. Our empirical results demonstrate that the proposed algorithm is very effective in optimizing edge application placement. In an edge system with 637 edge nodes and 563 end devices, our algorithm achieves 54% higher reduction of application latency than a previous decentralized algorithm. • Optimized placement of application components on cloud and edge devices. • Decentralized optimization algorithm using local knowledge and local modifications. • Auctions and distributed locking for synchronization. • Minimization of application latency. [ABSTRACT FROM AUTHOR]

The paper presents a new method of optimization by the Layered Algorithm (LA). The proposed algorithm reduces the initial area to the sub-area containing the optimum. The proposed technique is based on the classification of the optimized function values (data sampled by sensors). The classification method uses a two-dimensional three-state Cellular Automata (CA). The CA classifies all area points ascribed to the CA cells based on their values. Specification of the categorization layers to the data gives a possibility to identify the different levels areas. Consequently, after analysis, a sub-area containing the optimum can be designated. In this paper, the proposed algorithm is applied to find the location of the airborne contaminant source by analyzing the concentration of released substances reported by mobile sensors distributed over the domain of interest. The Gaussian dispersion model simulation of the contaminant dispersion in the urbanized area is applied to generate the data used to verify the efficiency of the proposed Layered Algorithm. The LA successfully estimates the sub-area of the considered domain where the contamination source is located, taking to account data from sensors solely. • Optimization method reducing the initial area to the sub-area containing the optimum. • Verification of the Layered Algorithm (LA) with Selected Benchmark Functions. • Analysis of the LA efficiency to localize the airborne contaminant source. • LA results assessment by the measures: classification and accuracy error, relevance. [ABSTRACT FROM AUTHOR]

• Formulate a non-cooperative game with both UEs and MECs as players. • Prove the existence of and convergence to a Nash equilibrium. • Develop a set of algorithms to find the Nash equilibrium. • Demonstrate numerical examples of non-cooperative games with and without MECs' participation. In a newly emerged fog computing environment, various user equipments (UE) enhance their computing power and extend their battery lifetime by computation offloading to mobile edge cloud (MEC) servers. Such an environment is distributed and competitive in nature. In this paper, we take a game theoretical approach to computation offloading optimization in a fog computing environment. Such an approach captures and characterizes the nature of a competitive environment. The main contributions of the paper can be summarized as follows. First, we formulate a non-cooperative game with both UEs and MECs as players. Each UE attempts to minimize the execution time of its tasks with an energy constraint. Each MEC attempts to minimize the product of its power consumption for computation and execution time for allocated tasks. Second, we develop a heuristic algorithm for a UE to determine its "heuristically" best response to the current situation, an algorithm for an MEC to determine its best response to the current situation, and an iterative algorithm to find the Nash equilibrium. Third, we prove that our iterative algorithm converges to a Nash equilibrium. We demonstrate numerical examples of our non-cooperative games with and without MECs' participation. We observe that our iterative algorithm always quickly converges to a Nash equilibrium. The uniqueness of our non-cooperative games is that the strategy set of a player can be discrete and the payoff function of a player can be obtained by a heuristic algorithm for combinatorial optimization. To the best of the author's knowledge, there has been no such investigation of non-cooperative games based on combinatorial optimization for computation offloading optimization in a fog computing environment. [ABSTRACT FROM AUTHOR]

Software systems rely on events for logging, coordination, handling unusual situations, and more. Monitoring event streams from systems that provide services can ensure the service complies with policies, regulations, and other business rules. Notably, monitoring to detect violations of rules as early as possible is much desired as, for example, the service may reclaim more resources from erring enactments. The primary goal of this paper is to develop techniques for detecting violations of time constraints as early as possible. We formalize a model for events and a language to specify constraints on event timing and data. We develop algorithms to detect violations of individual rules, then use a chase process to detect violations of acyclic sets of rules. We also present optimization techniques to reduce monitoring overhead. Finally, we implement and evaluate our algorithms through experiments to demonstrate our approach is feasible and beneficial. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

The MoF (Moment of Fluid) method is one of the most accurate approaches among various interface reconstruction algorithms. Alike other second order methods, the MoF method needs to solve an implicit optimization problem to obtain the optimal approximate interface, so an iteration process is inevitable under most circumstances. In order to solve the optimization efficiently, the properties of the objective function are worthy of studying. In 2D problems, the first order derivative has been deduced and applied in the previous researches. In this paper, the high order derivatives of the objective function are deduced on the convex polygon. We show that the n th ( n ≥ 2 ) order derivatives are discontinuous, and the number of the discontinuous points is two times the number of the polygon edge. A rotation algorithm is proposed to successively calculate these discontinuous points, thus the target interval where the optimal solution is located can be determined. Since the high order derivatives of the objective function are continuous in the target interval, the iteration schemes based on high order derivatives can be used to improve the convergence rate. Moreover, when iterating in the target interval, the value of objective function and its derivatives can be directly updated without explicitly solving the volume conservation equation. The direct update makes a further improvement of the efficiency especially when the number of edges of the polygon is increasing. The Halley's method, which is based on the first three order derivatives, is applied as the iteration scheme in this paper and the numerical results indicate that the CPU time is about half of the previous method on the quadrilateral cell and is about one sixth on the decagon cell. [ABSTRACT FROM AUTHOR]

In this paper, we study a maximization and a minimization problem associated with a Poisson boundary value problem. Optimal solutions in a set of rearrangements of a given function define stationary and stable flows of an ideal fluid in two dimensions. The main contribution of this paper is to determine the optimal solutions. At first, we determine a nearly optimal solution which is an approximation of the optimal solution when the problems are in low contrast regime. Secondly, for the high contrast regime, two optimization algorithms are developed. For the minimization problem, we prove that our algorithm converges to the global minimizer regardless of the initializer. The maximization algorithm is capable of deriving all local maximizers including the global one. Numerical experiments lead us to a conjecture about the location of the maximizers in the set of rearrangements of a function. [ABSTRACT FROM AUTHOR]

We introduce in this paper fixed-point proximity-gradient algorithms for solving a class of structured convex optimization problems arising from image restoration. The objective function of such optimization problems is the sum of three convex functions. We study in this paper the scenario where one of the convex functions involved is differentiable with a Lipschitz continuous gradient and another convex function is composed by an affine transformation. We first characterize the solutions of the optimization problem as fixed-points of a mapping defined in terms of the gradient of the differentiable function and the proximity operators of the other two functions. Then, a fixed-point proximity-gradient iterative scheme is developed based on the fixed-point equation which characterizes the solutions. We establish the convergence of the proposed iterative scheme by the notion of averaged nonexpansive operators. Moreover, we obtain that in general the proposed iterative scheme has O ( 1 k ) convergence rate in the ergodic sense and the sense of partial primal–dual gap. Under stronger assumptions on the convex functions involved the proposed iterative scheme will converge linearly. We in particular derive fixed-point proximity-gradient algorithms from the proposed iterative scheme. The quasi-Newton and the overrelaxation strategies are designed to accelerate the algorithms. Numerical experiments for the computerized tomography reconstruction problem demonstrate that the proposed algorithms perform favorably and the quasi-Newton as well as the overrelaxation strategies significantly accelerate the convergence of the algorithms. [ABSTRACT FROM AUTHOR]

The paper puts forward a new estimation method of modal parameters for dynamical systems. The problem of parameter estimation has been simplified to optimisation which is carried out using the ant colony system algorithm. The proposed method significantly constrains the solution space, determined on the basis of frequency plots of the receptance FRFs (frequency response functions) for objects presented in the frequency domain. The constantly growing computing power of readily accessible PCs makes this novel approach a viable solution. The combination of deterministic constraints of the solution space with modified ant colony system algorithms produced excellent results for systems in which mode shapes are defined by distinctly different natural frequencies and for those in which natural frequencies are similar. The proposed method is fully autonomous and the user does not need to select a model order. The last section of the paper gives estimation results for two sample frequency plots, conducted with the proposed method and the PolyMAX algorithm. [ABSTRACT FROM AUTHOR]

Highlights • A graphical method is proposed for optimal vibration distribution. • Existence and optimality of feasible controllers are addressed. • Performance limit of controllers is obtained. • Influence of constraints on optimal solutions is delineated. Abstract A number of design methodologies have been proposed for active control of vibrations. Most of the approaches proceed with formulating control design as optimization problems. These optimization-based methods are powerful and easy to use since numerical algorithms are usually available for finding solutions. However, the available methods have to be significantly modified to answering questions such as controller existence and achievable performance etc. This paper proposes a performance-limit-oriented solution developed for the problem of optimal distribution. A graphical approach is utilized for representation of the solutions. A number of important results upon existence of feasible controllers, optimality and performance limit of controllers, controller synthesis, as well as constraints handling are obtained; the puzzling issue of compromise between performance indices is resolved; the influence of constraints on optimal solutions are developed within the same graphical framework. This leads to a systematic design methodology to active vibration control for optimal distribution. The theoretical results are demonstrated through numerical examples and real time simulations. [ABSTRACT FROM AUTHOR]

This paper presents the design of an XYZ nano-manipulator as well as the model based high precision tracking control of the nano-manipulating system. Aiming at large range and high mechanical bandwidth, the proposed mechanical design employs compound bridge-type amplifiers to increase the workspace without significant drop of stiffness. To further improve the system tracking performance and avoid possible actuator saturations, a robust anti-windup tracking control architecture combining a parallel internal-model based controller and an anti-windup compensator is adopted for the trajectory tracking of the designed nano-manipulating system. As a theoretical extension on a recent result [17] , we further investigate the robust stability condition of the closed-loop system and formulate the optimization design of the anti-windup compensators as a two block H ∞ optimization problem solvable with the Nehari approach. Real time control experiments demonstrate excellent tracking performance and saturation compensation capability with tracking precision error less than 0.28 % , which significantly outperforms relevant algorithms in the literature. [ABSTRACT FROM AUTHOR]

Abstract: The Feedback Vertex Set problem asks whether a graph contains vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph of clique-width and a -expression of , we solve the Minimum Feedback Vertex Set problem in time . Our algorithm applies dynamic programming on a so-called -module decomposition of a graph, as defined by Rao (2008) [29], which is easily derivable from a-expression of the graph. The related notion of module-width of a graph is tightly linked to both clique-width and NLC-width, and in this paper we give an alternative equivalent characterization of module-width. [Copyright &y& Elsevier]

Sparse matrix–vector multiplication (SpMV) is an important issue in scientific computing and engineering applications. The performance of SpMV can be improved using parallel computing. The implementation and optimization of SpMV on GPU are research hotspots. Due to some irregularities of sparse matrices, the use of a single compression format is not satisfactory. The hybrid storage format can expand the range of adaptation of the compression algorithms. However, because of the imbalance of non-zero elements, the parallel computing capability of a GPU cannot be fully utilized. The parallel computing capability of a CPU is also rising due to increased number of cores in CPU. However, when a GPU is computing, the CPU controls the process instead of contributing to the computational work. It leads to under-utilization of the computing power of CPU. Due to the characteristics of the sparse matrices, the data can be split into two parts using the hybrid storage format to be allocated to CPU and GPU for simultaneous computing. In order to take full advantage of computing resources of CPU and GPU, the CPU–GPU heterogeneous computing model is adopted in this paper to improve the performance of SpMV. With analysis of the characteristics of CPU and GPU, an optimization strategy of sparse matrix partitioning using a distribution function is proposed to improve the computing performance of SpMV on the heterogeneous computing platform. The experimental results on two test machines demonstrate noticeable performance improvement. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the inverse problem on determining the spatial component of the source term in the hyperbolic equation with a time-dependent principal part. Based on a Carleman estimate for general hyperbolic operators, we prove a local stability result of Hölder type in both cases of partial boundary and interior observation data. Numerically, we adopt the classical Tikhonov regularization to reformulate the inverse problem into a related optimization problem, for which we develop an iterative thresholding algorithm by using the corresponding adjoint system. Numerical examples up to three spatial dimensions are presented to demonstrate the accuracy and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Without knowing the sparsity basis, Blind Compressive Sensing (BCS) can achieve similar results with those Compressive Sensing (CS) methods which rely on prior knowledge of the sparsity basis. However, BCS still suffers from two problems. First, compared with block-based sparsity, the global image sparsity ignores the local image features and BCS approaches based on it cannot obtain the competitive results. Second, since BCS only exploits the weaker sparsity prior than CS, the sampling rate required by BCS is still very high in practice. In this paper, we firstly propose a novel blind compressive sensing method based on block sparsity and nonlocal low-rank priors (BCS-BSNLR) to further reduce the sampling rate. In addition, we take alternating direction method of multipliers to solve the resulting optimization problem. Experimental results have demonstrated that the proposed algorithm can significantly reduce the sampling rate without sacrificing the quality of the reconstructed image. [ABSTRACT FROM AUTHOR]

The authors have previously shown that many traditional approaches to operational modal analysis (OMA) struggle to properly identify the modal damping ratios for bridges under traffic loading due to the interference caused by the driving frequencies of the traffic loads. This paper presents a novel methodology for modal parameter estimation in OMA that overcomes the problems presented by driving frequencies and significantly improves the damping estimates. This methodology is based on finding the power spectral density (PSD) of a given modal coordinate, and then dividing the modal PSD into separate regions, left- and right-side spectra. The modal coordinates were found using a blind source separation (BSS) algorithm and a curve-fitting technique was developed that uses optimization to find the modal parameters that best fit each side spectra of the PSD. Specifically, a pattern-search optimization method was combined with a clustering analysis algorithm and together they were employed in a series of stages in order to improve the estimates of the modal damping ratios. This method was used to estimate the damping ratios from a simulated bridge model subjected to moving traffic loads. The results of this method were compared to other established OMA methods, such as Frequency Domain Decomposition (FDD) and BSS methods, and they were found to be more accurate and more reliable, even for modes that had their PSDs distorted or altered by driving frequencies. [ABSTRACT FROM AUTHOR]

For classification problems based on microarray data, the data typically contains a large number of irrelevant and redundant features. In this paper, a new gene selection method is proposed to choose the best subset of features for microarray data with the irrelevant and redundant features removed. We formulate the selection problem as a L1-regularized optimization problem, based on a newly defined linear discriminant analysis criterion. Instead of calculating the mean of the samples, a kernel-based approach is used to estimate the class centroid to define both the between-class separability and the within-class compactness for the criterion. Theoretical analysis indicates that the global optimal solution of the L1-regularized criterion can be reached with a general condition, on which an efficient algorithm is derived to the feature selection problem in a linear time complexity with respect to the number of features and the number of samples. The experimental results on ten publicly available microarray datasets demonstrate that the proposed method performs effectively and competitively compared with state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The total variation (TV) model has been considered to be one of the most successful and representative model for compressive sensing (CS) sparse image reconstruction due to its advantage of preserving image edges. However, TV regularized term often favors piecewise constant solution and therefore it fails to preserve the details and textures. To overcome this defect and reconstruct the fine details, this paper proposes a two-dimensional CS sparse image reconstruction model by introducing the fractional-order TV (FrTV) regularization constraint into CS optimization problem. Furthermore, in order to achieve sparser representation flexibly, a combination of discrete wavelet transform and curvelet transform ℓ 1 -norm regularization is also incorporated into the cost function and a method for estimating the regularization parameter that trades off the two terms in the cost function is proposed. By using a smooth approximation of the ℓ 1 -norm, a gradient projection algorithm is derived to solve the combined FrTV and sparsifying transforms constrained minimization problem effectively. Compared with several state-of-the-art reconstruction algorithms, the proposed algorithm is more efficient and robust, not only yielding higher peak-signal-to-noise ratio, but also reconstructing the fine details and textures more efficiently. [ABSTRACT FROM AUTHOR]

Low-rank representation (LRR) and its variations have achieved great successes in subspace segmentation tasks. However, the segmentation processes of the existing LRR-related methods are all divided into two separated steps: affinity graphs construction and segmentation results obtainment. In the second step, normalize cut (Ncut) algorithm is used to get the final results based on the constructed graphs. This implies that the affinity graphs obtained by LRR-related algorithms may not be most suitable for Ncut, and the best results are not guaranteed to be achieved. In this paper, we propose a spectral clustering steered LRR representation algorithm (SCSLRR) which combines the objection functions of Ncut, K-means and LRR together. By solving a joint optimization problem, SCSLRR is able to find low-rank affinity matrices which are most beneficial for Ncut to get best segmentation results. The extensive experiments of subspace segmentation on several benchmark datasets show that SCSLRR dominates the related methods. [ABSTRACT FROM AUTHOR]

Spatial Quality Index (SQI) is a recently proposed video quality assessment metric that can predict video quality much close to subjective judgments. Since current video coding still has much redundancy in the sense of visual perception, in this paper, we incorporate SQI into video coding to further improve compression ratio without visual quality loss. Firstly, contributions of different human visual system (HVS) properties used in SQI are analyzed. Then two most important HVS properties, i.e. contrast masking effect (CME) and motion masking effect (MME), are extracted to measure perceptual-distortion D p in video coding. Finally, based on D p , a rate perceptual-distortion optimization (RpDO) algorithm is presented by adopting a suitable Lagrange multiplier from previous study. Experimental results show that, RpDO can averagely achieve 14% bitrate reduction when compared to HM14.0 under the same visual quality. At the same time, there is no significant change in the encoding time. [ABSTRACT FROM AUTHOR]

Abstract: Self-stabilizing algorithms for optimization problems can often be solved more easily using the distance-two model in which each vertex can instantly see the state information of all vertices up to distance two. This paper presents a new technique to emulate algorithms for the distance-two model on the distance-one model using the distributed scheduler with a slowdown factor of moves. Up until now the best transformer had a slowdown factor of moves. The technique is used to derive improved self-stabilizing algorithms for several graph domination problems. The paper also introduces a generalization of the distance-two model allowing a more space efficient transformer. [Copyright &y& Elsevier]

Abstract: In this paper, we give a lower bound guaranteeing exact matrix completion via singular value thresholding (SVT) algorithm. The analysis shows that when the parameter in SVT algorithm is beyond some finite scalar, one can recover some unknown low-rank matrices exactly with high probability by solving a strictly convex optimization problem. Furthermore, we give an explicit expression for such a finite scalar. This result in the paper not only has theoretical interests, but also guides us to choose suitable parameters in the SVT algorithm. [Copyright &y& Elsevier]

Abstract: Variable inertia vibration absorbers (VIVA) are previously used for the vibration control of single degree of freedom (dof) primary systems. The performance of such absorbers is studied in many investigations. This paper presents the dynamic modeling and simulation of a proposed modified design of such VIVA’s for the vibration control of two dof primary systems. Lagrange formulation is used to obtain its dynamic model in an analytical form. This model, which is highly nonlinear, is used to develop a computational algorithm to study the absorber performance characteristics. This algorithm is programmed and simulated in Matlab. The obtained results are numerically verified using SAMS2000 software. The effect of mass and stiffness of the proposed VIVA on its performance and tuning is discussed. An optimization algorithm is developed to select the best absorber parameters for vibration suppression of a specific primary system. The obtained results show a good agreement with those obtained using similar techniques. In addition, a linearized model of VIVA dynamics is developed, tested and simulated for the same data used in its nonlinear model. The relative deviation between results of the linear and nonlinear models is less than 1%, which confirms the realistic use of this linearized model. The experimental testing and verification of the simulation results of the proposed VIVA is the subject of another paper. [Copyright &y& Elsevier]

Abstract: In this paper, we have proposed an efficient wavelength rerouting algorithm for dynamic provisioning of lightpath. In wavelength-division multiplexed (WDM) networks rerouting of lightpath can be used to improve throughput and to reduce blocking probability. We have proposed a Lightpath Rerouting Algorithm (LRRA) for dynamic traffic in WDM optical networks. The results have shown that LRRA can improve blocking performance of the network. In this paper, low complexity algorithm has been developed which is used for the calculation of blocking probability of network. The proposed algorithm has also been applied on the realistic network such as NSFnet for calculation and optimization of blocking probability of the network. The results have also shown that the proposed algorithm can be implemented to huge networks for good blocking performance of the network. [Copyright &y& Elsevier]

Abstract: A mobile grid incorporates mobile devices into Grid systems. But mobile devices at present have severe limitations in terms of processing, memory capabilities and energy. Minimizing the energy usage in mobile devices poses significant challenges in mobile grids. This paper presents energy constrained resource allocation optimization for mobile grids. The goal of the paper is not only to reduce energy consumption, but also to improve the application utility in a mobile grid environment with a limited energy charge, ensuring battery lifetime and the deadlines of the grid applications. The application utility not only depends on its allocated resources including computation and communication resources, but also on the consumed energy, this leads to a coupled utility model, where the utilities are functions of allocated resources and consumed energy. Energy constrained resources allocation optimization is formulated as a utility optimization problem, which can be decomposed into two subproblems, the interaction between the two sub-problems is controlled through the use of a pricing variable. The paper proposes a price-based distributed energy constrained resources allocation optimization algorithm. In the simulation, the performance evaluation of our energy constrained resources allocation optimization algorithm is conducted. [Copyright &y& Elsevier]

Abstract: In this paper, we focus on the edit distance between two given strings where block-edit operations are allowed and better fitting to the human natural edit behaviors. Previous results showed that this problem is NP-hard when block moves are allowed. Various approximations to this problem have been proposed in recent years. However, this problem can be solved by the polynomial-time optimization algorithms if some reasonable restrictions are applied. The restricted variations which we consider involve character insertions, character deletions, block copies and block deletions. In this paper, three problems are defined with different measuring functions, which are , and . Then we show that with some preprocessing, the minimum block edit distances of these three problems can be obtained by dynamic programming in , and time, respectively, where n and m are the lengths of the two input strings. [Copyright &y& Elsevier]

The matrix model updating problem (MMUP), considered in this paper, concerns updating a symmetric second-order finite element model so that the updated model reproduces a given set of desired eigenvalues and eigenvectors by replacing the corresponding ones from the original model, and preserves the symmetry of the original model. In an optimization setting, this is a constrained nonlinear optimization problem. Taking advantage of the special structure of the constraint sets, it is first shown that the MMUP can be formulated as an optimization problem over the intersection of some special subspaces and linear varieties on the space of matrices. Using this formulation, an alternating projection method (APM) is then proposed and analyzed. The projections onto the involved subspaces and linear varieties are characterized. To the best of our knowledge, an alternating projection method for MMUP has not been proposed in the literature earlier. A distinct practical feature of the proposed method is that it is implementable using only a few measured eigenvalues and eigenvectors. No knowledge of the eigenvalues and eigenvectors of the associated quadratic matrix pencil is required. The results of our numerical experiments on both illustrative and benchmark problems show that the algorithm works well. The paper concludes with some future research problems. [Copyright &y& Elsevier]

Abstract: The paper presents quality of service (QoS) optimisation strategy for multi-criteria scheduling on the grid, based on a mathematical QoS model and a distributed iterative algorithm. Three QoS criteria are considered, namely payment, deadline and reliability, which are formulated as utility function. The optimisation problem is split into two parts: task optimisation performed on behalf of the user and resource optimisation performed on behalf of the grid. The strategy employs three types of agents: task agents responsible for task optimisation, computation resource and network resource agents responsible for resource optimisation. The agents apply economic models for optimisation purposes. Dynamic programming is used to optimise the total system utility function in terms of an iterative algorithm. The objective of multi-criteria scheduling is to maximise the global utility of the system. This paper proposes an iterative scheduling algorithm that is used to perform QoS optimisation-based multi-criteria scheduling. The proposed QoS optimisation-based multi-criteria scheduling problem solution has been practically examined by simulation experiments. [Copyright &y& Elsevier]

Abstract: Estimation of distribution algorithms (EDAs) are a wide-ranging family of evolutionary algorithms whose common feature is the way they evolve by learning a probability distribution from the best individuals in a population and sampling it to generate the next one. Although they have been widely applied to solve combinatorial optimization problems, there are also extensions that work with continuous variables. In this paper [this paper is an extended version of delaOssa et al. Initial approaches to the application of islands-based parellel EDAs in continuous domains, in: Proceedings of the 34th International Conference on Parallel Processing Workshops (ICPP 2005 Workshops), Oslo, 2005, pp. 580–587] we focus on the solution of the latter by means of island models. Besides evaluating the performance of traditional island models when applied to EDAs, our main goal consists in achieving some insight about the behavior and benefits of the migration of probability models that this framework allow. [Copyright &y& Elsevier]

A number of recent papers on approximation algorithms have used the square roots of unity, −1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2π/3, and ei4π/3, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in Goemans and Williamson (J. ACM 42 (1995) 1115–1145) to obtain near-optimum solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations xu−xv≡c (mod 3) and inequations xu−xv≢c (mod 3), where xu∈{0,1,2} for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a 0.793733-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee of 7/12+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3 arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+10−8 for the general problem (by Andersson et al. (J. Algorithms 39 (2001) 162–204)). It matches the guarantee of 0.836008 for Max-3-Cut found independently by de Klerk et al. (On approximate graph colouring and Max-k-Cut algorithms based on the ϑ-function, Manuscript, October 2000). We show that all these algorithms are in fact equivalent in the case of Max-3-Cut, and that our algorithm is the same as that of Andersson et al. in the more general case. [Copyright &y& Elsevier]

This paper studies recent modifications of the limited memory BFGS (L-BFGS) method for solving large scale unconstrained optimization problems. Each modification technique attempts to improve the quality of the L-BFGS Hessian by employing (extra) updates in a certain sense. Because at some iterations these updates might be redundant or worsen the quality of this Hessian, this paper proposes an updates criterion to measure this quality. Hence, extra updates are employed only to improve the poor approximation of the L-BFGS Hessian. The presented numerical results illustrate the usefulness of this criterion and show that extra updates improve the performance of the L-BFGS method substantially. [Copyright &y& Elsevier]

This paper presents a numerical algorithm for computing ISS Lyapunov functions for discrete-time systems which are input-to-state stable (ISS) on compact subsets of the state space. The algorithm relies on solving a linear optimisation problem and delivers a continuous and piecewise affine ISS Lyapunov function on a suitable triangulation covering the given compact set excluding a small neighbourhood of the origin. The objective of the linear optimisation problem is to minimise the ISS gain. It is shown that for every ISS system there exists a suitable triangulation such that the proposed algorithm terminates successfully. [ABSTRACT FROM AUTHOR]

This paper addresses the detection of periodic transients in vibration signals so as to detect faults in rotating machines. For this purpose, we present a method to estimate periodic-group-sparse signals in noise. The method is based on the formulation of a convex optimization problem. A fast iterative algorithm is given for its solution. A simulated signal is formulated to verify the performance of the proposed approach for periodic feature extraction. The detection performance of comparative methods is compared with that of the proposed approach via RMSE values and receiver operating characteristic (ROC) curves. Finally, the proposed approach is applied to single fault diagnosis of a locomotive bearing and compound faults diagnosis of motor bearings. The processed results show that the proposed approach can effectively detect and extract the useful features of bearing outer race and inner race defect. [ABSTRACT FROM AUTHOR]

This paper proposes a novel hybrid algorithm for simultaneously estimating the vehicle mass and road grade for hybrid electric bus (HEB). First, the road grade in current step is estimated using extended Kalman filter (EKF) with the initial state including velocity and engine torque. Second, the vehicle mass is estimated twice, one with EKF and the other with recursive least square (RLS) using the estimated road grade. A more accurate value of the estimated mass is acquired by weighting the trade-off between EKF and RLS. Finally, the road grade and vehicle mass thus obtained are used as the initial states for the next step, and two variables could be decoupled from the nonlinear vehicle dynamics by performing the above procedure repeatedly. Simulation results show that in different starting conditions, the proposed algorithm provides higher accuracy and faster convergence speed, compared with the results using EKF or RLS alone. [ABSTRACT FROM AUTHOR]

Data hiding techniques, which are classified into two groups: irreversible and reversible techniques, have been gained more and more attention recently. In which, reversible data hiding (RDH) is paid more attention since it is capable to recover original host images after revealing the secret data. However, there always is tradeoff between embedding capacity and image quality. The more secret data is embedded, the lower image quality is obtained. Therefore, in this paper, we propose a new RDH scheme to embed a large amount of secrets without causing dramatically damage to images. We develop an optimal exploiting modification direction matrix to modify the difference histogram. By carefully selecting image regions and using the optimal EMD table, the output image quality can be preserved while the embedding capacity of the scheme can be significantly enhanced. Experimental results demonstrated that our scheme outperforms previous schemes in terms of embedding capacity and image quality. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze the computational bottlenecks in discrete dislocation dynamics modeling (associated with segment–segment interactions as well as the treatment of free surfaces), discuss the parallelization and optimization strategies, and demonstrate the effectiveness of Graphical Processing Unit (GPU) computation in accelerating dislocation dynamics simulations and expanding their scope. Individual algorithmic benchmark tests as well as an example large simulation of a thin film are presented. [Copyright &y& Elsevier]

Abstract: This article considers recovery of signals that are sparse or approximately sparse in terms of a (possibly) highly overcomplete and coherent tight frame from undersampled data corrupted with additive noise. We show that the properly constrained -analysis optimization problem, called analysis Dantzig selector, stably recovers a signal which is nearly sparse in terms of a tight frame provided that the measurement matrix satisfies a restricted isometry property adapted to the tight frame. As a special case, we consider the Gaussian noise. Further, under a sparsity scenario, with high probability, the recovery error from noisy data is within a log-like factor of the minimax risk over the class of vectors which are at most s sparse in terms of the tight frame. Similar results for the analysis LASSO are shown. The above two algorithms provide guarantees only for noise that is bounded or bounded with high probability (for example, Gaussian noise). However, when the underlying measurements are corrupted by sparse noise, these algorithms perform suboptimally. We propose new algorithms for reconstructing signals that are nearly sparse in terms of a tight frame in the presence of bounded noise combined with sparse noise, and present corresponding recovery guarantees. The analysis in this paper is based on the restricted isometry property adapted to a tight frame, which is a natural extension to the standard restricted isometry property. [Copyright &y& Elsevier]

Abstract: This paper presents a preconditioner for non-overlapping Schwarz methods applied to the Helmholtz problem. Starting from a simple analytic example, we show how such a preconditioner can be designed by approximating the inverse of the iteration operator for a layered partitioning of the domain. The preconditioner works by propagating information globally by concurrently sweeping in both directions over the subdomains, and can be interpreted as a coarse grid for the domain decomposition method. The resulting algorithm is shown to converge very fast, independently of the number of subdomains and frequency. The preconditioner has the advantage that, like the original Schwarz algorithm, it can be implemented as a matrix-free routine, with no additional preprocessing. [Copyright &y& Elsevier]

Abstract: Optimizing the acquisition matrix is useful for compressed sensing of signals that are sparse in overcomplete dictionaries, because the acquisition matrix can be adapted to the particular correlations of the dictionary atoms. In this paper a novel formulation of the optimization problem is proposed, in the form of a rank-constrained nearest correlation matrix problem. Furthermore, improvements for three existing optimization algorithms are introduced, which are shown to be particular instances of the proposed formulation. Simulation results show notable improvements and superior robustness in sparse signal recovery. [Copyright &y& Elsevier]

Abstract: The paper describes an algorithm for PDE-constrained optimization that controls numerical errors using error estimates and grid adaptation during the optimization process. A key aspect of the algorithm is the use of adjoint variables to estimate errors in the first-order optimality conditions. Multilevel optimization is used to drive the optimality conditions and their estimated errors below a specified tolerance. The error estimate requires two additional adjoint solutions, but only at the beginning and end of each optimization cycle. Moreover, the adjoint systems can be formed and solved with limited additional infrastructure beyond that found in typical PDE-constrained optimization algorithms. The approach is general and can accommodate both reduced-space and full-space formulations of the optimization problem. The algorithm is illustrated using the inverse design of a nozzle constrained by the quasi-one-dimensional Euler equations. [Copyright &y& Elsevier]

Abstract: In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for solving large combinatorial optimization problems on GPU-enhanced multi-core machines. B&B is a tree-based optimization method that uses four operators (selection, branching, bounding and pruning) to build and explore a highly irregular tree representing the solution space. In our previous works, we have proposed a GPU-accelerated approach in which only a single CPU core is used and only the bounding operator is performed on the GPU device. Here, we extend the approach (LL-GB&B) in order to minimize the CPU–GPU communication latency and thread divergence. Such an objective is achieved through a GPU-based fine-grained parallelization of the branching and pruning operators in addition to the bounding one. The second contribution consists in investigating the combination of a GPU with multi-core processing. Two scenarios have been explored leading to two approaches: a concurrent (RLL-GB&B) and a cooperative one (PLL-GB&B). In the first one, the exploration process is performed concurrently by the GPU and the CPU cores. In the cooperative approach, the CPU cores prepare and off-load to GPU pools of tree nodes using data streaming while the GPU performs the exploration. The different approaches have been extensively experimented on the Flowshop scheduling problem. Compared to a single CPU-based execution, LL-GB&B allows accelerations up to ( 160) for large problem instances. Moreover, when combining multi-core and GPU, we figure out that using RLL-GB&B is not beneficial while PLL-GB&B enables an improvement up to 36% compared to LL-GB&B. [Copyright &y& Elsevier]

Abstract: Integral equation methods for the solution of partial differential equations, when coupled with suitable fast algorithms, yield geometrically flexible, asymptotically optimal and well-conditioned schemes in either interior or exterior domains. The practical application of these methods, however, requires the accurate evaluation of boundary integrals with singular, weakly singular or nearly singular kernels. Historically, these issues have been handled either by low-order product integration rules (computed semi-analytically), by singularity subtraction/cancellation, by kernel regularization and asymptotic analysis, or by the construction of special purpose “generalized Gaussian quadrature” rules. In this paper, we present a systematic, high-order approach that works for any singularity (including hypersingular kernels), based only on the assumption that the field induced by the integral operator is locally smooth when restricted to either the interior or the exterior. Discontinuities in the field across the boundary are permitted. The scheme, denoted QBX (quadrature by expansion), is easy to implement and compatible with fast hierarchical algorithms such as the fast multipole method. We include accuracy tests for a variety of integral operators in two dimensions on smooth and corner domains. [Copyright &y& Elsevier]

• The combined fronthaul network improves the quality of service by the edge computing. • The correction factor meets the physical constraints in network planning. • The performance of the network can be greatly improved by the proposed algorithm. The rapid development of time-sensitive applications, such as autopilot, telemedicine and industrial automation, demands more stringent requirements on end-to-end delay. Therefore, low-delay planning of 5G networks is supposed to be a crucial stage. In this paper, a low-delay layout planning based on the nonlinear decreasing inertia weight particle swarm optimization algorithm (NL-wPSO) is demonstrated. By iteratively calculating the velocity and position of each particle, the proposed algorithm can optimize the layout of AAUs in the fronthaul network. Thereby, the distance between the AAUs and edge computing server will be shortened. Compared to the basic PSO, the simulation results indicate a significant reduction on transmission delay. [ABSTRACT FROM AUTHOR]

Abstract: Interval dynamic response analysis of vehicle-bridge interaction system with uncertain parameters is studied in this paper. The bridge''s and vehicle''s parameters are considered as interval variables. A half-car model is used to represent a moving vehicle and the bridge is assumed as a simply supported Euler–Bernoulli beam. By introducing the interval algorithm into the dynamic analysis of vehicle-bridge interaction system, the expressions of the midpoint value, interval width, lower and upper bounds of interval bridge dynamic response are developed. The lower and upper bounds are respectively the minimum and maximum values of bridge dynamic response, which can also be determined by optimization approaches. A heuristic optimization method, a new particle swarm optimization method with low-discrepancy sequence initialized particles and high-order nonlinear time-varying inertia weight and constant acceleration coefficients (LHNPSO), is then developed to find the bounds of bridge displacement. Examples are used to illustrate the effectiveness of the presented methods and Monte-Carlo simulations are implemented to validate the computational results. The effects of individual system parameters on bridge response are also investigated. [Copyright &y& Elsevier]

Abstract: Traffic classification in the Internet is a crucial mechanism necessary to support network services. Using Ternary Content-Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs concurrently match the packet headers against the rules in a classification database providing high throughput unparalleled by software-based solutions. The complexity of packet classification policies has been growing rapidly as the number of Internet services continues to increase. Many complex classification policies are naturally represented in a hierarchical fashion, where different layers perform classification based on the administrative domain and the traffic QoS parameters. However, multiple levels of classification hierarchy incur high lookup latency while high TCAM memory requirements of flattened classification policies is a major issue since TCAMs have very limited capacity. In this paper we focus on the fundamental tradeoff between the TCAM space and the number of lookups in the TCAM classification policies. We consider two optimization problems of dual nature: the first problem is to minimize the number of TCAM entries subject to the constraint on the maximum number of levels in the policy hierarchy; the second problem is to minimize the number of levels in the policy hierarchy subject to the constraint on the maximum number of TCAM entries. We propose efficient algorithms for these problems, which do not require any hardware changes. To the best of our knowledge, this is the first work to study these problems. We also show experimental results that support our findings. [Copyright &y& Elsevier]

Abstract: The solution of time-dependent PDE-constrained optimization problems subject to unsteady flow equations presents a challenge to both algorithms and computing power. In this paper we present an all-at-once approach where we solve for all time-steps of the discretized unsteady Stokes problem at once. The most desirable feature of this approach is that for all steps of an iterative scheme we only need approximate solutions of the discretized Stokes operator. This leads to an efficient scheme which exhibits mesh-independent behaviour. [Copyright &y& Elsevier]

Abstract: This paper introduces an automatic feature extraction algorithm for bearing fault diagnosis using correlation filtering-based matching pursuit. This algorithm is described and investigated in theory and practice on both simulated and real bearing vibration signals. First, the vibration model for rolling bearing with fault is derived. Then, the numerical simulation signal being taken as an example, the principle of matching pursuit is mathematically explained and its drawbacks are analyzed. Afterward, to enhance the similarity of model related to the bearing faulty impulses, the model shape parameters are optimized using spectrum kurtosis and smoothing index. After that, the model with optimum shape and period parameters is taken as a template to approximate the impulses in faulty bearing signal. Finally, based on maximizing correlation principle, the optimized cycle parameter being as impuls e repetition period is matched up. The proposed method has been successfully applied in actual vibration signals of rolling element bearing with different faults. [Copyright &y& Elsevier]

Abstract: The paper studies the benefits of multi-path content delivery from a rate-distortion efficiency perspective. We develop an optimization framework for computing transmission schedules for streaming media packets over multiple network paths that maximize the end-to-end video quality, for the given bandwidth resources. We comprehensively address the two prospective scenarios of content delivery with packet path diversity. In the context of sender-driven systems, our framework enables the sender to compute at every transmission instance the mapping of packets to network paths that meets a rate constraint while minimizing the end-to-end distortion. In receiver-driven multi-path streaming, our framework enables the client to dynamically decide which packets, if any, to request for transmission and from which media servers, such that the end-to-end distortion is minimized for a given transmission rate constraint. Via simulation experiments, we carefully examine the performance of the scheduling framework in both multi-path delivery scenarios. We demonstrate that the optimization framework closely approaches the performance of an ideal streaming system working at channel capacity with an infinite play-out delay. We also show that the optimization leads to substantial gains in rate-distortion performance over a conventional content-agnostic scheduler. Through the concept of error-cost performance for streaming a single packet, we provide another useful insight into the operation of the optimization framework and the conventional scheduling system. [Copyright &y& Elsevier]