Search

Time-varying resource allocation allows users to define their own unique resource requirement plans during different time periods. This mode of allocation can increase the flexibility of resource usage and reduce resource usage costs for users. Moreover, combining this approach with an auction mechanism can enable resource providers to obtain greater social welfare and benefits; therefore, such resource allocation has become a hot topic in cloud computing. This paper addresses the problem of time-varying batch virtual machine (VM) allocation and pricing in the cloud. Specifically, (1) we propose a novel integer programming model for the time-varying batch VM allocation problem, and (2) we design two truthful auction mechanisms to solve the allocation and pricing problem in a competitive environment. The optimal mechanism includes a dynamic programming (DP)-based resource allocation algorithm and a Vickrey–Clarke–Groves (VCG)-based payment price algorithm. Meanwhile, we also design a greedy mechanism that includes a dominant-resource-based allocation algorithm and a dichotomy-based payment price algorithm. We prove the economic characteristics, including truthfulness and individual rationality, of the above two mechanisms. Furthermore, we prove the approximation ratio of the allocation algorithm in the greedy mechanism. Compared to state-of-the-art research, our approach is characterized by high social welfare, a high served user ratio and a short execution time. [ABSTRACT FROM AUTHOR]

While conducting bandwidth allocation over elastic optical data center network EODCN, it is important to balance the revenue of cloud service providers and the connection performance of tenants. This paper proposed a bandwidth allocation algorithms to effectively assign optical bandwidth for multiple connection requests based on subcarriers so as to maximize revenue. Firstly, on the basis of a revenue model and a concept of virtual subcarrier, it constructed an integer linear programming formulation of the studied bandwidth allocation problem. Then, it proposed a dynamic programming-based algorithm and a heuristics-based algorithm correspondingly, which respectively focus on achieving maximum net revenue and gaining better time efficiency. Finally, it conducted simulations to validate the efficiency of the designed algorithms. The simulation results show that both of the proposed algorithms are superior to the existed methods in system revenue obtaining in bandwidth allocation over EODCN. [ABSTRACT FROM AUTHOR]

In this paper, we propose a trustworthy service provisioning scheme for Safety-as-a-Service (Safe-aaS) infrastructure in IoT-based intelligent transport systems. Typically, a Safe-aaS infrastructure provides customized safety-related decisions dynamically to multiple end-users using the concept of decision virtualization. We consider road transportation as the application environment of Safe-aaS to generate trustworthy decisions. On the other hand, the efficiency and accuracy of the decisions generated depend on the security, privacy, and trustworthiness of the participating sensor nodes and the route through which data transit. We propose a trust evaluation model to compute the trustworthiness of the data generated from these nodes. Further, we consider direct and indirect trust mechanisms for each of the sensor nodes and update their trust measures at regular intervals of time. Based on these measures, we evaluate the trust of each data item sourced from the network. We formulate an integer linear programming (ILP) model to select the optimal data for decision-making, while alleviating the effects of illegitimate sensor nodes. Further, we show that the formulated ILP problem is NP-hard and use a dynamic programming approach to solve the problem. Experimental results show that our proposed trust evaluation model exhibits more than 8% attack detection rate and 13% reduction in false attack detection rate in a network with 50% malicious nodes, compared to the benchmark schemes. The proposed trustworthy data selection algorithm outperforms different existing greedy approaches. [ABSTRACT FROM AUTHOR]

As an important part of container logistics, quay cranes (QCs) are crucial equipment in multimodal container transportation. The scheduling and allocation of QCs determine the operational efficiency of container terminals. By analyzing the way quay cranes are operated, this paper establishes a mixed-integer dynamic rolling-horizon programming model for the scheduling and allocation of QCs and proposes use of a genetic algorithm and two improved firefly algorithms based on segment encoding technology to formulate an optimum QC scheduling scheme. In doing so, the improved approach has made QC control more efficient and balanced. [ABSTRACT FROM AUTHOR]

With the assumption that each appointment patient up in clinic arrives on time, this paper investigates the appointment scheduling problem with no-show. An integer programming model is established with the numbers of appointment patient and probability distribution of remaining patients at each slot as optimization variables. The objective function includes the benefits of serving patients, the patient waiting time costs, and system overtime expenses. By relaxing the coupled constraints about probability distribution of remaining patients at each slot, this paper proposes a Lagrangian relaxation method to solve the model with a dynamic programming algorithm solving the relaxation problem and a sub-gradient method solving the dual problem. Numerical experiments show that the algorithm can find the optimal solution for small scale problems, and that the best solution from the proposed algorithm is better than the one in the related literature for large scale problems. [ABSTRACT FROM AUTHOR]

Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model that subsumes different labeling styles. We show that labeling a single line of the network is NP-hard, even if we make very restricting requirements about the labeling style that is used with this model. For a restricted variant of that model, we then introduce an efficient algorithm that optimally labels a single line with respect to a given cost function. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps. [ABSTRACT FROM AUTHOR]

Security-constrained unit commitment (SCUC), as one of key components in power system operation, is being widely applied in vertically integrated utilities and restructured power systems. The efficient solution framework is to implement iterations between a master problem (unit commitment) and subproblems (network security evaluations). In industrial applications, both Lagrangian relaxation and mixed-integer programming are commonly applied for the unit commitment problem, and both linear sensitivity factor and Benders cut methods are used to generate additional constraints in the phase of network security evaluations. This paper evaluates capabilities and performances of each algorithm through technical discussion and numerical testing. Special topics on the large-scale SCUC engine development are also discussed in this paper, such as input data screening, inactive constrains elimination, contingency management, infeasibility handling, parallel computing, and model simplification. This paper will benefit academic researchers, software developers, and system operators when they design, develop and assess effective models and algorithms for solving large-scale SCUC problems. [ABSTRACT FROM PUBLISHER]

Abstract: Irreducible decomposition of monomial ideals has an increasing number of applications from biology to pure math. This paper presents the Slice Algorithm for computing irreducible decompositions, Alexander duals and socles of monomial ideals. The paper includes experiments showing good performance in practice. [Copyright &y& Elsevier]

Because of its ease of administration, role-based access control (RBAC) has become the norm to enforcing security in most of today's organizations. For implementing RBAC, it is important to devise a complete and correct set of roles. This task, known as role engineering, has been identified as one of the costliest components in deploying RBAC. A key problem with respect to role engineering is that there is no formal metric for measuring the goodness/interestingness of the devised set of roles. Recently, Vaidya et al. [26], formally define the role mining problem (RMP) as the problem of discovering an optimal set of roles from existing user permissions, and analyze its theoretical bounds. Essentially, given a user-permission assignment (UPA), the basic RMP is to discover the user-role assignment relation (UA) and role-permission assignment relation (PA) such that the number of roles required is minimum. In this paper, we present another interesting and useful problem, called the edge-RMP, with a different minimality objective. The edge-RMP, requires the discovery of a complete and correct set of roles such that the discovered |UA|+|PA| is the minimum possible. Minimal |UA|+|PA| is a useful metric as it would minimize the administrative burden since less number of assignments need to be managed. Although the basic-RMP and the edge-RMP appear to be related problems, we demonstrate with concrete examples that they are, in fact, independent of each other. We prove that the edge-RMP is an NP-hard problem by reducing the known “vertex cover problem” to the decision version of the edge-RMP. Another important contribution of this paper is to provide a binary integer programming solution to this problem by showing that the edge-RMP can be formulated in that form. As a result, one can directly borrow existing implementation solutions for binary integer programming and guide further research in this direction. We also propose a heuristic solution for large scale problems, and experimentally validate our algorithm. [ABSTRACT FROM AUTHOR]

The introduction of edge-finding techniques was a significant development in constraint-based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge-finding algorithms for cumulative scheduling and shows that Nuijten's edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time O(n²k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge-finder specification. The paper also proposes the first extended edge-finding algorithms that run in time O(n²k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning. [ABSTRACT FROM AUTHOR]

In the ring loading problem, traffic demands are given for each pair of nodes in an undirected ring network and a flow is routed in either of two directions, clockwise and counterclockwise. The load of an edge is the sum of the flows routed through the edge and the objective of the problem is to minimize the maximum load on the ring. Myung [J. Korean OR and MS Society, 23 (1998), pp. 49–62 (in Korean)] has presented an efficient algorithm for solving a problem where flow is restricted to integers. However, the proof for the validity of the algorithm in their paper is long and complicated and as the paper is written in Korean, its accessibility is very limited. In this paper, we slightly modify their algorithm and provide a simple proof for the correctness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper focuses on sensor scheduling for state estimation, which consists of a network of noisy sensors and a discrete-time linear system with process noise. As an energy constraint, only a subset of sensors can take a measurement at each time step. These measurements are fused into a common state estimate using a Kalman filter and the goal is to schedule the sensors to minimize the estimation error at a terminal time. A simple approach is to greedily choose sensors at each time step to minimize the estimation error at the next time step. Recent work has shown that this greedy algorithm outperforms other well known approaches. Results have been established to show that the estimation error is a submodular function of the sensor schedule; submodular functions have a diminishing returns property that ensures the greedy algorithm yields near optimal performance. As a negative result, we show that most commonly-used estimation error metrics are not, in general, submodular functions. This disproves an established result. We then provide sufficient conditions on the system for which the estimation error is a submodular function of the sensor schedule, and thus the greedy algorithm yields performance guarantees. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm for a ship scheduling problem, obtained from a Swedish ship-owning company. The algorithm uses the Dantzig-Wolfe decomposition method for linear programming. The subprograms are simple network flow problems that are solved by dynamic programming. The master program in the decomposition algorithm is an LP problem with only zero-one elements in the matrix and the right-hand side. Integer solutions are not guaranteed, but generation and solution of a large number of problems indicates that the frequency of fractional solutions is as small as 1-2 per cent. Problems with about 40 ships and 50 cargoes are solved in about 2.5 minutes on an IBM 7090. In order to resolve the fractional cases, some integer programming experiments have been made. The results will be reported in a forthcoming paper. [ABSTRACT FROM AUTHOR]

Rollout algorithms have demonstrated excellent performance on a variety of dynamic and discrete optimization problems. Interpreted as an approximate dynamic programming algorithm, a rollout algorithm estimates the value-to-go at each decision stage by simulating future events while following a heuristic policy, referred to as the base policy. While in many cases rollout algorithms are guaranteed to perform as well as their base policies, there have been few theoretical results showing additional improvement in performance. In this paper, we perform a probabilistic analysis of the subset sum problem and 0-1 knapsack problem, giving theoretical evidence that rollout algorithms perform strictly better than their base policies. Using a stochastic model from the existing literature, we analyze two rollout methods that we refer to as the exhaustive rollout and consecutive rollout, both of which employ a simple greedy base policy. We prove that both methods yield a significant improvement in expected performance after a single iteration of the rollout algorithm, relative to the base policy. [ABSTRACT FROM AUTHOR]

The vehicle travel time in time varying network not only depends on the distance between the nodes but also the time of day. In this paper, we developed a method satisfying first-in first-out property to deal with time period(s) crossing. The travel time can be deduced with it directly. The problem was formulated and a novel dynamic programming heuristics was presented to solve it. The algorithm can balance solution quality and computation time with parameter H. From the simulation results on 10 randomly generated cases, the new method can greatly improve the solution of nearest neighborhood algorithm within a very short time. When H=2, the average solution is improved 11%, while the computation time is 1.34s. It also can be improved 17% within less than 2s with H=3. [ABSTRACT FROM AUTHOR]

This paper deals with finding most vital links of a network which carries flows over time (also called "dynamic flows"). Given a network and a time horizon T, Single Most Vital Link Over Time (SMVLOT) problem looks for a link whose removal results in greatest decrease in the value of maximum flow over time (dynamic maximum flow) up to time horizon T between two terminal nodes. SMVLOT problem is formulated as a mixed binary linear programming problem. This formulation is extended to a general case called k-Most Vital Links Over Time (KMVLOT) problem, in which we look for finding those κ links whose removal makes greatest decrease in the value of maximum flow over time. A Benders decomposition algorithm is proposed for solving SMVLOT and KMVLOT problems. For the case of SMVLOT problem, the proposed algorithm is improved to a fully combinatorial algorithm by adopting an iterative method for solving existing integer programming problem. However, our experimental results showed the superiority of proposed methods. [ABSTRACT FROM AUTHOR]

We present a hybridization of two different approaches applied to the well-known Capacitated Facility Location Problem (CFLP). The Artificial Bee algorithm (BA) is used to select a promising subset of locations (warehouses) which are solely included in the Mixed Integer Programming (MIP) model. Next, the algorithm solves the subproblem by considering the entire set of customers. The hybrid implementation allows us to bypass certain inherited weaknesses of each algorithm, which means that we are able to find an optimal solution in an acceptable computational time. In this paper we demonstrate that BA can be significantly improved by use of the MIP algorithm. At the same time, our hybrid implementation allows the MIP algorithm to reach the optimal solution in a considerably shorter time than is needed to solve the model using the entire dataset directly within the model. Our hybrid approach outperforms the results obtained by each technique separately. It is able to find the optimal solution in a shorter time than each technique on its own, and the results are highly competitive with the state-of-the-art in large-scale optimization. Furthermore, according to our results, combining the BA with a mathematical programming approach appears to be an interesting research area in combinatorial optimization. [ABSTRACT FROM AUTHOR]

Prize-collecting arc routing problems are arc routing problems where, in addition to the cost function, there is a profit function on the edges that must only be taken into account the first time that an edge is traversed. This work presents the clustered prize-collecting arc routing problem where there are clusters of arcs and it is required that all or none of the edges of a cluster be serviced. The paper studies properties and dominance conditions used for formulating the problem as a linear integer program. An exact algorithm for finding an optimal solution to the problem is also proposed. At the root node of the enumeration tree, the algorithm generates upper and lower bounds obtained from solving an iterative linear programming-based algorithm in which violated cuts are generated when possible. A simple heuristic that generates feasible solutions provides lower bounds at each iteration. The numerical results from a series of computational experiments with various types of instances illustrate the good behavior of the algorithm. Over 75% of the instances were solved at the root node, and the remaining instances were solved with a small additional computational effort. [ABSTRACT FROM AUTHOR]

Abstract   We present an algorithm that takes I/Os (sort(N)=Θ((N/(DB))log  M/B (N/B)) is the number of I/Os it takes to sort N data items) to compute a tree decomposition of width at most k, for any graph G of treewidth at most k and size N, where k is a constant. Given such a tree decomposition, we use a dynamic programming framework to solve a wide variety of problems on G in I/Os, including the single-source shortest path problem and a number of problems that are NP-hard on general graphs. The tree decomposition can also be used to obtain an optimal separator decomposition of G. We use such a decomposition to perform depth-first search in G in  I/Os. As important tools that are used in the tree decomposition algorithm, we introduce flippable DAGs and present an algorithm that computes a perfect elimination ordering of a k-tree in I/Os. The second contribution of our paper, which is of independent interest, is a general and simple framework for obtaining I/O-efficient algorithms for a number of graph problems that can be solved using greedy algorithms in internal memory. We apply this framework in order to obtain an improved algorithm for finding a maximal matching and the first deterministic I/O-efficient algorithm for finding a maximal independent set of an arbitrary graph. Both algorithms take I/Os. The maximal matching algorithm is used in the tree decomposition algorithm. [ABSTRACT FROM AUTHOR]

The distribution of a limited rate of high-pressure gas to gas-lifted wells, while respecting injection bounds and activation precedence constraints, consists of a mixed-integer nonlinear programming problem. This paper proposes a mixed-integer linear formulation obtained by piece-wise-linearizing the nonlinear functions, thereby allowing the use of integer programming algorithms. Valid inequalities for the convex hull of feasible solutions are derived from knapsack covers, for which exact and approximate lifting procedures yield stronger inequalities. Numerical results show that these cover-based cuts reduce the number of nodes explored in a branch-and-bound search. [ABSTRACT FROM AUTHOR]

Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from other facets of master cyclic group polyhedra (group cuts) do not seem to be as useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied. [ABSTRACT FROM AUTHOR]

Abstract: A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex colorings of trees arise in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree. When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one, and what are the convex colorings which are “closest” to it. In this paper we study a natural definition of this distance—the recoloring distance, which is the minimal number of color changes at the vertices needed to make the coloring convex. We show that finding this distance is NP-hard even for a colored string (a path), and for some other interesting variants of the problem. In the positive side, we present algorithms for computing the recoloring distance under some natural generalizations of this concept: the first generalization is the uniform weighted model, where each vertex has a weight which is the cost of changing its color. The other is the non-uniform model, in which the cost of coloring a vertex v by a color d is an arbitrary non-negative number . Our first algorithms find optimal convex recolorings of strings and bounded degree trees under the non-uniform model in time which, for any fixed number of colors, is linear in the input size. Next we improve these algorithm for the uniform model to run in time which is linear in the input size for a fixed number of bad colors, which are colors which violate convexity in some natural sense. Finally, we generalize the above result to hold for trees of unbounded degree. [Copyright &y& Elsevier]

This paper solves FC_2TDC, the two-staged fixed-orientation two-dimensional cutting stock problem. FC_2TDC is a variant of the constrained two-dimensional cutting problem where each piece is produced, in the final cutting pattern, by at most two cuts, and each piece has a fixed orientation. It is solved by an algorithm that combines a strip-generation procedure with beam search (BS). BS, which is a truncated branch-andbound, investigates a subset of elite nodes and permanently fathoms the others. It chooses the elite nodes based on an evaluation operator. The importance of the evaluation operator on the performance of BS is highlighted by comparing a local beam search (LBS) that uses a priority cost-evaluation operator to a global beam search (GBS) that adopts a global cost-evaluation operator. Computational results, based on several medium and large instances, further show that LBS provides good solutions, whereas GBS gives (near) optimal solutions within reasonable computational time. [ABSTRACT FROM AUTHOR]

Abstract: In recent years, several approaches to computing the value of p-length gap-weighted kernel have been presented, such as trie-based approach, suffix kernel, and range sum technique. Although other approaches can achieve better performance in some cases, suffix kernel technique is still an efficient approach in this context. In this paper, we present a series of dynamic programming algorithms based on suffix kernel to compute gapped string kernels. Given strings s and t, and a gap penalty λ, all-length gap-weighted kernel can be calculated in time O(|s||t|) with our algorithms. Moreover, some new string kernels belonging to the family of gapped string kernels are presented, including all-length and p-length match-weighted kernels, and their variants. Based on the suffix kernel technique, we can compute all-length match-weighted kernel in time O(|s||t|), and then p-length kernel in time O(p|s||t|) using the relationship between all-length and p-length kernels. Furthermore, for p-length match-weighted kernel and its variant, a bit-parallel technique is used to reduce the complexity from O(p|s||t|) to O(⌈pk/w⌉|s||t|), where w is the word size of the machine (e.g. 32 or 64 in practice) and k is determined by the longest matching subsequence of two strings s and t. The empirical results suggest that the suffix kernel technique is an important and useful approach to computing gapped string kernels. [Copyright &y& Elsevier]

In this paper, we consider the problem of checking the feasibility of a set of n real-time tasks while provisioning for timely recovery from (at most) k transient faults. We extend the well-known processor demand approach to take into account the extra overhead that may be induced by potential recovery operations under Earliest-Deadline-First scheduling. We develop a necessary and sufficient test using a dynamic programming technique. An improvement upon the previous solutions is to address and efficiently solve the case where the recovery blocks associated with a given task do not necessarily have the same execution time. We also provide an online version of the algorithm that does not require a priori knowledge of release times. The online algorithm runs in O(m ∙ k²) time, where m is the number of ready tasks. We extend the framework to periodic execution settings: We derive a sufficient condition that can be checked efficiently for the feasibility of periodic tasks in the presence of faults. Finally, we analyze the case where the recovery blocks are to be executed nonpreemptively and we formally show that the problem becomes intractable under that assumption. [ABSTRACT FROM AUTHOR]

We consider two related nonlinear integer programming problems arising in series–parallel reliability systems: the constrained redundancy problem and the cost minimization problem. We propose in this paper an efficient method for solving these two types of nonlinear integer programming problems. The proposed convergent Lagrangian method combines Lagrangian relaxation with a duality reduction technique. An outer approximation method is used to search for the optimal dual solution and to generate Lagrangian bounds of the primal problem. To reduce the duality gap, we derive a special partition scheme by exploiting the inherent monotonicity and separability of the problem. Furthermore, a special optimality criterion is adopted to improve feasible solutions and to fathom integer subboxes. Computational results show that the algorithm is capable of solving large-scale optimization problems in series–parallel reliability systems. Comparison numerical results with other existing methods are also reported. [ABSTRACT FROM AUTHOR]

Focusing on embedded applications, scratchpad memories (SPMs) look like a best-compromise solution when taking into account performance, energy consumption, and die area. The main challenge in SPM design is to optimally map memory locations to scratchpad locations. This paper describes an algorithm to solve such a mapping problem by means of dynamic programming applied to a synthesizable hardware architecture. The algorithm works by mapping segments of external memory to physically partitioned banks of an on-chip SPM; this architecture provides significant energy savings. The algorithm does not require any user-set bound on the number of partitions and takes into account partitioning overhead. Improving on previous solutions, execution time is polynomial in the number of memory locations, even in the most general solving policy. This has the major practical advantage of allowing an arbitrary number of scratchpad segments, something that was impossible with previous methods, whose running time is exponential to this number. Strategies to optimize memory requirements and speed of the algorithm are exploited. Additionally, we integrate this algorithm in a complete and automated design, simulation, and synthesis flow. [ABSTRACT FROM AUTHOR]

One of the main ingredients of interior-point methods is the generation of iterates in a neighborhood of the central path. Measuring how close the iterates are to the central path is an important aspect of such methods and it is accomplished by using proximity measure functions. In this paper, we propose a unified presentation of the proximity measures and a study of their relationships and computational role when using a generic primal-dual interior-point method for computing the analytic center for a standard linear optimization problem. We demonstrate that the choice of the proximity measure can affect greatly the performance of the method. It is shown that we may be able to choose the algorithmic parameters and the central-path neighborhood radius (size) in such a way to obtain comparable results for several measures. We discuss briefly how to relate some of these results to nonlinear programming problems. [ABSTRACT FROM AUTHOR]

This paper presents a new robust Dynamic Programming (DP)-based recognition algorithm that is quite suitable for menu-driven recognition applications with small vocabulary size (typically less than 50). When compared to the conventional Dynamic Time Warping (DTW)-based recognizer, the proposed algorithm shows significantly improved recognition accuracy in speaker-independent cases. In addition, when compared to the conventional Hidden Markov Model (HMM) -based recognizer, the proposed algorithm requires smaller computational amount and parameter file size, while maintaining almost the same recognition rate for command recognition applications with small vocabulary size in hand-held consumer devices. [ABSTRACT FROM AUTHOR]

The Bayesian Information Criterion (BIC) is a widely adopted method for audio segmentation, and has inspired a number of dominant algorithms for this application. At present, however, literature lacks in analytical and experimental studies on these algorithms. This paper tries to partially cover this gap.Typically, BIC is applied within a sliding variable-size analysis window where single changes in the nature of the audio are locally searched. Three different implementations of the algorithm are described and compared: (i) the first keeps updated a pair of sums, that of input vectors and that of square input vectors, in order to save computations in estimating covariance matrices on partially shared data; (ii) the second implementation, recently proposed in literature, is based on the encoding of the input signal with cumulative statistics for an efficient estimation of covariance matrices; (iii) the third implementation consists of a novel approach, and is characterized by the encoding of the input stream with the cumulative pair of sums of the first approach.Furthermore, a dynamic programming algorithm is presented that, within the BIC model, finds a globally optimal segmentation of the input audio stream.All algorithms are analyzed in detail from the viewpoint of the computational cost, experimentally evaluated on proper tasks, and compared. [Copyright &y& Elsevier]

This paper presents both application and comparison of the metaheuristic techniques to Generation Expansion Planning (GEP) problem. The Metaheuristic techniques such as the Genetic Algorithm, Differential Evolution, Evolutionary Programming, Evolutionary Strategy, Ant Colony Optimization, Particle Swarm Optimization, Tabu Search, Simulated Annealing, and Hybrid Approach are applied to solve GEP problem. The original GEP problem is modified using the proposed methods Virtual Mapping Procedure (VMP) and Penalty Factor Approach (PFA), to improve the efficiency of the metaheuristic techniques. Further, Intelligent Initial Population Generation (IIPG), is introduced in the solution techniques to reduce the computational time. The VMP, PFA, and IIPG are used in solving all the three test systems. The GEP problem considered synthetic test systems for 6-year, 14-year, and 24-year planning horizon having five types of candidate units. The results obtained by all these proposed techniques are compared and validated against conventional Dynamic Programming and the effectiveness of each proposed methods has also been illustrated in detail. [ABSTRACT FROM AUTHOR]

Abstract: In VLSI layout design, certain nets in a given net set are required to propagate their signals within a tolerable skew of delays. Though the delay of the signal on a wire is determined by a complex environment, it is hard to satisfy this requirement unless all the concerned nets are routed within a certain skew of length. In this paper, we propose L-equidistance routing, which routes the concerned nets with a prescribed length L. After a basic technique of L-equidistance routing of a single 1-sink net, an algorithm is presented for the channel routing of plural multi-sink nets. The key idea is in the symmetric-slant grid interconnect scheme by which the problem is reduced to a grid routing problem. In L-equidistance routing of a channel, the total length of a n-sink net is not unique for . An algorithm based on dynamic programming to solve this minimization problem is presented. Then, L-equidistance switch-box routing is discussed based on the L-equidistance channel routing. Algorithms are explained on the Euclidean space. But it is shown that a straightforward transformation of the routes to those on the Manhattan grid is possible keeping the property of equidistance. The proposing channel routing algorithm was implemented and applied to random data to demonstrate their ability. [Copyright &y& Elsevier]

Abstract: The paper is concerned with the problem of automatic detection and correction of inconsistent or out of range data in a general process of statistical data collection. The proposed approach is able to deal with hierarchical data containing both qualitative and quantitative values. As customary, erroneous data records are detected by formulating a set of rules. Erroneous records should then be corrected, by modifying as less as possible the erroneous data, while causing minimum perturbation to the original frequency distributions of the data. Such process is called imputation. By encoding the rules with linear inequalities, we convert imputation problems into integer linear programming problems. The proposed procedure is tested on a real-world case of census. Results are extremely encouraging both from the computational and from the data quality point of view. [Copyright &y& Elsevier]

Excess delay that each component of a design can tolerate under a given timing constraint is referred to as delay budget Delay budgeting.. has been widely exploited to improve the design quality in very large scale integrated computer-aided design flow. The objective of the delay-budgeting problem investigated in this paper is to maximize the total delay budget assigned to each node in a directed acycle graph under a given timing constraint. Due to the discreteness of the timing of the components in the libraries during design-optimization flow, discrete solution for delay budgeting is essential. We present an optimal integer delay-budgeting algorithm. We prove that the problem can be solved optimally in polynomial time. In addition, we look at different extensions of the delay-budgeting problem, such as maximization of weighted summation of, delay budgets assigned to the nodes with constraints on the lower and upper bounds on the delay budget allocated to each node. We prove that for both aforementioned extensions, our algorithm can produce an optimal integer solution in polynomial time. Our algorithm 15 generic and can be applied at different design tasks at different lads of abstraction. We applied our proposed optimal delay-budgeting algorithm in library mapping during data- path synthesis on a field programmable gate array (FPGA) plat- form, using. pre optimized cores of FPGA libraries. For each application, we go through synthesis and place and route stages in order to obtain accurate results. Our optimal algorithm outperforms the zero-slack algorithm (Nair et al. 1989) in terms of area by 10% on average for all applications. In some applications, optimal delay budgeting can speedup runtime of place_and_mute tip to two times. [ABSTRACT FROM AUTHOR]