Search

• 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]

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]

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]

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]

• 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]

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]

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]

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]

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: 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]

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]

Highlights • Propose a novel ordinal metric learning methodology (i.e. OSPL) from the viewpoint of representation learning. • Present an alternating optimization algorithm to solve the OSPL model with complexity analysis. • Experimentally evaluate the effectiveness and superiority of the proposed method. Graphical abstract Abstract Ordinal metric learning (OML) is an important research branch of metric learning and has attracted increasing attention due to its wide applications where there typically exists a global order (i.e. , ordinal) relationship among the data classes, such as human age estimation and head pose recognition, etc. Although several works have been proposed to perform OML, they suffer from two critical drawbacks: 1) only the local ordinal relationships among classes rather than the global one are considered, and 2) the very time-consuming semi-definite programming is commonly involved. To avoid these shortcomings, in this paper we propose a novel OML approach, named ordinal space projection learning (OSPL) by representing one class with its neighbor classes whose representation weights are proportional to their class distance (i.e. , absolute label difference), in which the neighboring ordinal class similarities are taken into account in their reconstruction. Then, we present an alternating optimization algorithm to solve the proposed method to learn an ordinal distance space. Finally, extensive experiments on ordinal estimation tasks demonstrate effectiveness and superiority of the proposed method. [ABSTRACT FROM AUTHOR]

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]

This paper proposes smoothness-constrained globally-optimal tracking of objects. Unlike previous globally-optimal tracking methods, the proposed method can evaluate the smoothness of object trajectories so that the smoothness at a frame can (1) be computed from object detections between the frame and any other frame (e.g., detections even between a long time-interval) and (2) be evaluated simultaneously with multiple neighboring frames. The former and latter properties are called high-order smoothness and high-order constraints, respectively. The high-order smoothness allows us to evaluate the smoothness robustly against noise in detections. The high-order constraints are useful because tracking optimization gets more stable as constraints increase in number. Moreover, smoothness can be evaluated between detections at each frame (i.e., framewise optimization) rather than between short tracks, each of which consists of detections at subsequent frames. Globally-optimal tracking is achieved on a graph where each node corresponds to a detected object region so that detected regions are temporally connected through frames in order to find optimal tracking paths. It is difficult for previous globally-optimal methods to use dynamic features (e.g., velocity), which are required to evaluate smoothness between frames. This is because different tracking paths passing through a node require this node to have inconsistent dynamic features. That is, since the different tracking paths in a graph correspond to spatially-different paths in a scene, each of the different tracking paths has its own dynamic feature at this intersection node. These inconsistent features at the intersection node are prohibited for global optimization on a graph. In the proposed method, such a node is divided such that each divided node has a unique dynamic feature. With public datasets, the proposed method can improve the rate of successful tracking. [ABSTRACT FROM AUTHOR]

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]

Many recent advances in multi-target tracking have grown concern over latent corresponding relation among observations, e.g. social relationship. To handle long-term occlusion within group and tracking failure caused by interaction of targets, various correlations among tracklets need to be exploited. In this paper, a paratactic–serial tracklet graph (PSTG) theory is proposed for inter-tracklet analysis in multi-target tracking to avoid tracking failure caused by long-term occlusion within group or crossing trajectories. Contrary to recent approaches, a novel PSTG is defined to describe the correlation among all tracklets in spatio-temporal domain to model the mutual influence among trajectories. Paratactic–tracklet graph extends the potential relationship among tracklets which show similar motion patterns in spatio-temporal neighbor. Serial–tracklet graph enhances the integrity and continuity of trajectories which represent two trajectory fragments of a certain target in different periods. Furthermore, a PSTG-based multi-label optimization algorithm is presented to make the trajectory estimation more accurate. A PSTG energy is minimized by multi-label optimization, including group, integrity and spatio-temporal constraints. Experiments demonstrate the anti-occlusion performance of the proposed approach on several public datasets and actual surveillance sequences, and achieve competitive results by quantitative evaluation. [ABSTRACT FROM AUTHOR]

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: 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: 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: The pixel labeling problems in computer vision are often formulated as energy minimization tasks. Algorithms such as graph cuts and belief propagation are prominent; however, they are only applicable for specific energy forms. For general optimization, Markov Chain Monte Carlo (MCMC) based simulated annealing can estimate the minima states very slowly. This paper presents a sampling paradigm for faster optimization. First, in contrast to previous MCMCs, the role of detailed balance constraint is eliminated. The reversible Markov chain jumps are essential for sampling an arbitrary posterior distribution, but they are not essential for optimization tasks. This allows a computationally simple window cluster sample. Second, the proposal states are generated from combined sets of local minima which achieve a substantial increase in speed compared to uniformly labeled cluster proposals. Third, under the coarse-to-fine strategy, the maximum window size variable is incorporated along with the temperature variable during simulated annealing. The proposed window annealing is experimentally shown to be many times faster and capable of finding lower energy compared to the previous Gibbs and Swendsen-Wang cut (SW-cut) sampler. In addition, the proposed method is compared with other deterministic algorithms like graph cut, belief propagation, and spectral method in their own specific energy forms. Window annealing displays competitive performance in all domains. [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: Active appearance models (AAMs) are useful for face tracking for the advantages of detailed face interpretation, accurate alignment and high efficiency. However, they are sensitive to initial parameters and may easily be stuck in local minima due to the gradient-descent optimization, which makes the AAM based face tracker unstable in the presence of large pose deviation and fast motion. In this paper, we propose to combine the view-based AAMs with two novel temporal filters to overcome the limitations. First, we build a new view space based on the shape parameters of AAMs, instead of the model parameters controlling both the shape and appearance, for the purpose of pose estimation. Then the Kalman filter is used to simultaneously update the pose and shape parameters for a better fitting of each frame. Second, we propose a temporal matching filter which is twofold. The inter-frame local appearance constraint is incorporated into AAM fitting, where the mechanism of the active shape model (ASM) is also implemented in a unified framework to find more accurate matching points. Moreover, we propose to initialize the shape with correspondences found by a random forest based local feature matching. By introducing the local information and temporal correspondences, the twofold temporal matching filter improves the tracking stability when confronted with fast appearance changes. Experimental results show that our algorithm is more pose robust than basic AAMs and some state-of-art AAM based methods, and that it can also handle large expressions and non-extreme illumination changes in test video sequences. [Copyright &y& Elsevier]

Abstract: A finite -frame variety consists of real or complex matrices satisfying and for all . This paper introduces an approximate geometric gradient descent procedure over these varieties, which is powered by minimization algorithms for the frame operator distance and recent characterizations of these varietiesʼ tangent spaces. For almost all compatible pairings , we demonstrate that minimization of the frame operator distance converges linearly under a threshold, we derive a process for constructing the orthogonal projection onto these varietiesʼ tangent spaces, and finally demonstrate that the approximate gradient descent procedure converges. Finally, we apply this procedure to numerically construct Grassmannian frames and Welch bound equality sequences with low mutual coherence. [Copyright &y& Elsevier]

Abstract: This paper addresses the problem of scheduling non-preemptive moldable tasks to minimize the stretch of the tasks in an online non-clairvoyant setting. To the best of the authors’ knowledge, this problem has never been studied before. To tackle this problem, first the sequential subproblem is studied through the lens of the approximation theory. An algorithm, called DASEDF, is proposed and, through simulations, it is shown to outperform the first-come, first-served scheme. Furthermore, it is observed that machine availability is the key to getting good stretch values. Then, the moldable task scheduling problem is considered, and, by leveraging the results from the sequential case, another algorithm, DBOS, is proposed to optimize the stretch while scheduling moldable tasks. This work is motivated by a task scheduling problem in the context of parallel short sequence mapping which has important applications in biology and genetics. The proposed DBOS algorithm is evaluated both on synthetic data sets that represent short sequence mapping requests and on data sets generated using log files of real production clusters. The results show that the DBOS algorithm significantly outperforms the two state-of-the-art task scheduling algorithms on stretch optimization. [Copyright &y& Elsevier]

Abstract: In this paper, we show that the convex optimization problem can be solved by the proximal point algorithm in a finite number of steps under the assumption that the solution set is a set of weak sharp minima. [Copyright &y& Elsevier]

Abstract: This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) and Cartis et al. (2010) show that at most iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the convergence behavior of the Schwarz waveform relaxation (SWR) algorithms for solving PDEs with time delay. We choose the reaction diffusion equations with a constant time delay as the underlying model problem and try to derive optimized transmission conditions of Robin type. To this end, we propose a new method to get quasi-optimized parameter involved in the transmission conditions and it is shown that this method is essentially different from the existing ones. Moreover, when the situation is reduced into the heat equations with a constant delay, we show that this method results in a more efficient quasi-optimized parameter. Numerical results are provided to validate our theoretical results. [Copyright &y& Elsevier]

Abstract: Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in time, while the previous best runs in time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in time , where is the alphabet size and with . This new time bound is better than the previous best for small alphabets, including the very important case where (i.e., the case of DNA strings). [Copyright &y& Elsevier]

Abstract: The photorealistic modeling of large-scale objects, such as urban scenes, requires the combination of range sensing technology and digital photography. In this paper, we attack the key problem of camera pose estimation, in an automatic and efficient way. First, the camera orientation is recovered by matching vanishing points (extracted from 2D images) with 3D directions (derived from a 3D range model). Then, a hypothesis-and-test algorithm computes the camera positions with respect to the 3D range model by matching corresponding 2D and 3D linear features. The camera positions are further optimized by minimizing a line-to-line distance. The advantage of our method over earlier work has to do with the fact that we do not need to rely on extracted planar facades, or other higher-order features; we are utilizing low-level linear features. That makes this method more general, robust, and efficient. We have also developed a user-interface for allowing users to accurately texture-map 2D images onto 3D range models at interactive rates. We have tested our system in a large variety of urban scenes. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new non-parametric combined segmentation and registration method. The shapes to be registered are implicitly modeled with level set functions and the problem is cast as an optimization one, combining a matching criterion based on the active contours without edges for segmentation (Chan and Vese, 2001) and a nonlinear-elasticity-based smoother on the displacement vector field. This modeling is twofold: first, registration is jointly performed with segmentation since guided by the segmentation process; it means that the algorithm produces both a smooth mapping between the two shapes and the segmentation of the object contained in the reference image. Secondly, the use of a nonlinear-elasticity-type regularizer allows large deformations to occur, which makes the model comparable in this point with the viscous fluid registration method. In the theoretical minimization problem we introduce, the shapes to be matched are viewed as Ciarlet–Geymonat materials. We prove the existence of minimizers of the introduced functional and derive an approximated problem based on the Saint Venant–Kirchhoff stored energy for the numerical implementation and solved by an augmented Lagrangian technique. Several applications are proposed to demonstrate the potential of this method to both segmentation of one single image and to registration between two images. [Copyright &y& Elsevier]

Abstract: We consider the minimization of a smooth convex function regularized by the composite prior models. This problem is generally difficult to solve even if each subproblem regularized by one prior model is convex and simple. In this paper, we present two algorithms to effectively solve it. First, the original problem is decomposed into multiple simpler subproblems. Then, these subproblems are efficiently solved by existing techniques in parallel. Finally, the result of the original problem is obtained by averaging solutions of subproblems in an iterative framework. The proposed composite splitting algorithms are applied to the compressed MR image reconstruction and low-rank tensor completion. Numerous experiments demonstrate the superior performance of the proposed algorithms in terms of both accuracy and computation complexity. [Copyright &y& Elsevier]

Abstract: In this paper we describe a method that can be used for Minimum Bayes Risk (MBR) decoding for speech recognition. Our algorithm can take as input either a single lattice, or multiple lattices for system combination. It has similar functionality to the widely used Consensus method, but has a clearer theoretical basis and appears to give better results both for MBR decoding and system combination. Many different approximations have been described to solve the MBR decoding problem, which is very difficult from an optimization point of view. Our proposed method solves the problem through a novel forward–backward recursion on the lattice, not requiring time markings. We prove that our algorithm iteratively improves a bound on the Bayes risk. [Copyright &y& Elsevier]

Abstract: Multiobjective discrete programming is a well-known family of optimization problems with a large spectrum of applications. The linear case has been tackled by many authors during the past few years. However, the polynomial case has not been studied in detail due to its theoretical and computational difficulties. This paper presents an algebraic approach for solving these problems. We propose a methodology based on transforming the polynomial optimization problem to the problem of solving one or more systems of polynomial equations and we use certain Gröbner bases to solve these systems. Different transformations give different methodologies that are theoretically stated and compared by some computational tests via the algorithms that they induce. [Copyright &y& Elsevier]

Abstract: Peer-to-Peer(P2P) streaming has been proved a popular and efficient paradigm of Internet media streaming. In some applications, such as an Internet video distance education system, there are multiple media sources which work alternately. A fundamental problem in designing such kind of P2P streaming system is how to achieve fast source switching so that the startup delay of the new source can be minimized. In this paper, we propose an efficient solution to this problem. We model the source switch process, formulate it into an optimization problem and derive its theoretical optimal solution. Then we propose a practical greedy algorithm, named fast source switch algorithm, which approximates the optimal solution by properly interleaving the data delivery of different media sources. The algorithm can adapt to the dynamics and heterogeneity of real Internet environments. We have carried out extensive simulations on various real-trace P2P overlay topologies to demonstrate the effectiveness of our model and algorithm. The simulation results show that our proposed algorithm outperforms the normal source switch algorithm by reducing the source switch time by 20%–30% without bringing extra communication overhead. The reduction in source switching time is more obvious as the network scale increases. [Copyright &y& Elsevier]

Abstract: This paper shows that shared-coin algorithms can be combined to optimize several complexity measures, even in the presence of a strong adversary. By combining shared coins of Bracha and Rachman (1991)  and of Aspnes and Waarts (1996) , this yields a shared-coin algorithm, and hence, a randomized consensus algorithm, with individual work and total work, using single-writer registers. This improves upon each of the above shared coins (where the former has a high cost for individual work, while the latter reduces it but pays in the total work), and is currently the best for this model. Another application is to prove a construction of Saks, Shavit, and Woll (1991) , which combines a shared-coin algorithm that takes time in failure-free executions, with one that takes time in executions where at most processes fail, and another one that takes time in any other execution. [Copyright &y& Elsevier]

Abstract: In this paper, we study the inverse sorting problem with bound constraints under the -norm and the Hamming distance. For the problem under the -norm, an -time algorithm is presented. For the problem under the Hamming distance, we first show that it has an -time lower bound in the comparison model; and then, we present an -time algorithm. Both of the presented algorithms improve the previous upper bounds from . [Copyright &y& Elsevier]

Abstract: Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input. In this paper we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include k-Path, k-Cycle, k-Exact Cycle, k-Short Cheap Tour, k-Graph Minor Order Test, k-Cutwidth, k-Search Number, k-Pathwidth, k-Treewidth, k-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters. [Copyright &y& Elsevier]

We propose here an improved multi-objective optimisation model that considers eco-environmental water demand (EWD) for allocating water resources in a river basin over the long term. The model considers economic, social, and environmental objectives, and it improves on traditional optimisation methods by emphasizing not only the water demand of the artificial ecosystem but also that of the natural ecosystem. Water resource constraints are considered. The hybrid genetic simulated annealing algorithms (HGSAA) technique incorporates a genetic algorithm (GA) and a simulated annealing (SA) algorithm, which have strong local and global searching abilities, in order to solve the highly non-linear model and avoid local and premature convergence. In the method, the water demands of users in the planning year serve as the basis for long-term optimisation using a forecasting procedure. In this study, the combined forecasting method based on the principle of optimal combination is built to forecast domestic and industrial water demands. The proposed model and method are subsequently used in a companion paper to optimise water allocation in the Haihe River basin in China [An eco-environmental water demand based model for optimising water resources using hybrid genetic simulated annealing algorithms. Part II. Model application and results 90 (8), 2612¿2619]. [Copyright &y& Elsevier]

Abstract: In this paper we present a new primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we obtain the currently best known iteration bound for the algorithm with small-update method, namely, , which is as good as the linear analogue. [Copyright &y& Elsevier]

Abstract: Factorial designs are arguably the most widely used designs in scientific investigations. Generalized minimum aberration (GMA) and uniformity are two important criteria for evaluating both regular and non-regular designs. The generation of GMA designs is a non-trivial problem due to the sequential optimization nature of the criterion. Based on an analytical expression between the generalized wordlength pattern and a uniformity measure, this paper converts the generation of GMA designs to a constrained optimization problem, and provides effective algorithms for solving this particular problem. Moreover, many new designs with GMA or near-GMA are reported, which are also (nearly) optimal under the uniformity measure. [Copyright &y& Elsevier]

Multimedia event detection is the task of detecting a specific event of interest in an user-generated video on websites. The most fundamental challenge facing this task lies in the enormously varying quality of the video as well as the high-level semantic abstraction of event inherently. In this paper, we decompose the video into several segments and intuitively model the task of complex event detection as a multiple instance learning problem by representing each video as a "bag" of segments in which each segment is referred to as an instance. Instead of treating the instances equally, we associate each instance with a reliability variable to indicate its importance and then select reliable instances for training. To measure the reliability of the varying instances precisely, we propose a visual-semantic guided loss by exploiting low-level feature from visual information together with instance-event similarity based high-level semantic feature. Motivated by curriculum learning, we introduce a negative elastic-net regularization term to start training the classifier with instances of high reliability and gradually taking the instances with relatively low reliability into consideration. An alternative optimization algorithm is developed to solve the proposed challenging non-convex non-smooth problem. Experimental results on standard datasets, i.e., TRECVID MEDTest 2013 and TRECVID MEDTest 2014, demonstrate the effectiveness and superiority of the proposed method to the baseline algorithms. • A visual-semantic guided loss is proposed to measure reliability of instance for event detection. • Training begins with high-reliability instances and gradually added instances of low reliability. • Promising experimental results show the effectiveness and superiority of the proposed method. [ABSTRACT FROM AUTHOR]

Abstract: Recently great attention has been given to point-of-failure swap rerouting, an efficient technique for routing in the presence of transient failures. According to this technique, a message follows the normal routing table information unless the next hop has failed; in this case, it is redirected towards a precomputed link, called swap; once this link has been crossed, normal routing is resumed. The choice of the swap edge is done according to some optimization criteria on the resulting new route. The amount of precomputed information required in addition to the routing table is rather small: a single link per each destination. Several efficient serial algorithms have been presented to compute this information for several optimization criteria (, , , ). Only the algorithm corresponding to has been efficiently implemented in a distributed environment, while for the other optimization criteria no distributed solution has been devised yet. In this paper we present protocols, based on a new strategy, that allow the efficient distributed computation of all the optimal swap edges under , , . Although considerably more difficult than , these problems can be solved with the same cost. In systems allowing long messages, we develop solution protocols based on the same strategy that use only messages without increasing the total amount of transmitted data items. [Copyright &y& Elsevier]

Abstract: In this paper we propose a derivative-free optimization algorithm based on conditional moments for finding the maximizer of an objective function. The proposed algorithm does not require calculation or approximation of any order derivative of the objective function. The step size in iteration is determined adaptively according to the local geometrical feature of the objective function and a pre-specified quantity representing the desired precision. The theoretical properties including convergence of the method are presented. Numerical experiments comparing with the Newton, Quasi-Newton and trust region methods are given to illustrate the effectiveness of the algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a scheduling problem for divisible loads originating from single or multiple sites on arbitrary networks. We first propose a generalized mathematical model and formulate the scheduling problem as an optimization problem with an objective to minimize the processing time of the loads. We derive a number of theoretical results on the solution of the optimization problem. On the basis of these first set of results, we propose an efficient algorithm for scheduling divisible loads using the concept of load balancing via virtual routing for an arbitrary network configuration. The proposed algorithm has three major attractive features. Firstly, the algorithm is simple to realize and can be implemented in a distributed fashion. The second one is in its style of working by avoiding the need for generating a timing diagram explicitly for any complex networks having an arbitrary network topology. The last one is its capability of handling divisible loads originating from both single and multiple sites. When divisible loads originate from a single node, we compare the proposed algorithm with a recently proposed RAOLD algorithm which is based on minimum cost spanning tree [J. Yao, V. Bharadwaj, Design and performance analysis of divisible load scheduling strategies on arbitrary graphs, Cluster Computing 7(2) (2004) 191–207]. When divisible loads originate from multiple sites, we test the performance on sparse, medium and densely connected networks. This is the first time in the divisible load theory (DLT) literature that such a generic approach for handling divisible loads originating from multiple sites on arbitrary networks employing load balancing via virtual routing is attempted. [Copyright &y& Elsevier]

Abstract: This paper focuses on solving large size combinatorial optimization problems using a Grid-enabled framework called ParadisEO–CMW (llel and tributed on top on ondor and the aster orker Framework). The latter is an extension of ParadisEO, an open source framework originally intended to the design and deployment of parallel hybrid meta-heuristics on dedicated clusters and networks of workstations. Relying on the Condor–MW framework, it enables the execution of these applications on volatile heterogeneous computational pools of resources. The motivations, architecture and main features will be discussed. The framework has been experimented on a real-world problem: feature selection in near-infrared spectroscopic data mining. It has been solved by deploying a multi-level parallel model of evolutionary algorithms. Experimentations have been carried out on more than 100 PCs originally intended for education. The obtained results are convincing, both in terms of flexibility and easiness at implementation, and in terms of efficiency, quality and robustness of the provided solutions at run time. [Copyright &y& Elsevier]