Data caching in the cloud is an efficient way to improve the QoS of diverse data applications. However, this benefit is not freely available, given monetary cost to manage the caches in the cloud. In this paper, we study the data caching problem in the cloud that is driven by the monetary cost reduction, instead of the hit rate under limited capacity as in traditional cases. In particular, given a stream of requestsRto a shared data item, we present a shortest-path based optimal algorithm that can minimize the total transfer and caching costs within O(mn) time for off-line case, here m represents the number of nodes in the network, while n is the length of the request stream. The cost model in this computation is semi-homo, which indicates that all pairs of nodes have the same transfer cost, but each cache server node has its own caching cost rate. Our off-line algorithm improves the previous results not only in reducing the time complexity from O(m2n) to O(mn), but also in relaxing the cost model to be semi-homogeneous, rendering the algorithm more practical in reality. Furthermore, we also study this problem in its online form, and by extending the anticipatory caching idea, we propose a 2-competitive online algorithm based on the same cost model and show its tightness by giving a lower bound of the competitive ratio as 2 - o(1) for any deterministic online algorithm. We provably achieve these results with our deep insights into the problem and careful analysis of the solution algorithms, together with a trace-based study to evaluate their performance in reality.

In this paper we consider the data caching problem in next generation data services in the cloud, which is characterized by using monetary cost and access trajectory information to control cache replacements, instead of exploiting capacityoriented strategies as in traditional research. In particular, given a stream of requests to a shared data item with respect to a homogeneous cost model, we first propose a fast off-line algorithm using dynamic programming techniques. The proposed algorithm can generate optimal schedule within O(mn) timespace complexity to cache, migrate as well as replicate the shared data item to serve an n-length request sequence with minimum cost in a fully connected m-node network, substantially improving the previous results. Additionally, we also study this problem in its online form, and present a 3-competitive online algorithm by leveraging a speculative caching idea. The algorithm can serve an online request in constant time, and is space efficient in O(m) as well, rendering it to be more practical in reality. Our research complements the shortage of similar research in literature on this problem.

Informally, a set of abstractions of a state space S is additive if the distance between any two states in S is always greater than or equal to the sum of the corresponding distances in the abstract spaces. The first known additive abstractions, called disjoint pattern databases, were experimentally demonstrated to produce state of the art performance on certain state spaces. However, previous applications were restricted to state spaces with special properties, which precludes disjoint pattern databases from being defined for several commonly used testbeds, such as Rubik's Cube, TopSpin and the Pancake puzzle. In this paper we give a general definition of additive abstractions that can be applied to any state space and prove that heuristics based on additive abstractions are consistent as well as admissible. We use this new definition to create additive abstractions for these testbeds and show experimentally that well chosen additive abstractions can reduce search time substantially for the (18,4)-TopSpin puzzle and by three orders of magnitude over state of the art methods for the 17-Pancake puzzle. We also derive a way of testing if the heuristic value returned by additive abstractions is provably too low and show that the use of this test can reduce search time for the 15-puzzle and TopSpin by roughly a factor of two.

In this paper, we study the possibility of designing non-trivial random CSP models by exploiting the intrinsic connection between structures and typical-case hardness. We show that constraint consistency, a notion that has been developed to improve the efficiency of CSP algorithms, is in fact the key to the design of random CSP models that have interesting phase transition behavior and guaranteed exponential resolution complexity without putting much restriction on the parameter of constraint tightness or the domain size of the problem. We propose a very flexible framework for constructing problem instances withinteresting behavior and develop a variety of concrete methods to construct specific random CSP models that enforce different levels of constraint consistency. A series of experimental studies with interesting observations are carried out to illustrate the effectiveness of introducing structural elements in random instances, to verify the robustness of our proposal, and to investigate features of some specific models based on our framework that are highly related to the behavior of backtracking search algorithms.

In this paper, we investigate the space complexity of the Estimation of Distribution Algorithms (EDAs), a class of sampling-based variants of the genetic algorithm. By analyzing the nature of EDAs, we identify criteria that characterize the space complexity of two typical implementation schemes of EDAs, the factorized distribution algorithm and Bayesian network-based algorithms. Using random additive functions as the prototype, we prove that the space complexity of the factorized distribution algorithm and Bayesian network-based algorithms is exponential in the problem size even if the optimization problem has a very sparse interaction structure.

In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model. For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.

The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to constraints on the subgoal size. Each subgoal in the database provides a tight lower bound on the cost of achieving it. For a given state in the search space, all possible subgoals are looked up in the pattern database, with the maximum cost over all lookups being the lower bound. For sliding tile puzzles, the database enumerates all possible patterns containing N tiles and, for each one, contains a lower bound on the distance to correctly move all N tiles into their correct final location. For the 15‐Puzzle, iterative‐deepening A* with pattern databases(N ="8) reduces the total number of nodes searched on a standard problem set of 100 positions by over 1000‐fold.

The paper is in three parts. First, we use simple adversary arguments to redevelop and explore some of the no-free-lunch (NFL) theorems and perhaps extend them a little. Second, we clarify the relationship of NFL theorems to algorithm theory and complexity classes such as NP. We claim that NFL is weaker in the sense that the constraints implied by the conjectures of traditional algorithm theory on what an evolutionary algorithm may be expected to accomplish are far more severe than those implied by NFL. Third, we take a brief look at how natural evolution relates to computation and optimization. We suggest that the evolution of complex systems exhibiting high degrees of orderliness is not equivalent in difficulty to optimizing hard (in the complexity sense) problems, and that the optimism in genetic algorithms (GAs) as universal optimizers is not justified by natural evolution. This is an informal tutorial paper--most of the information presented is not formally proven, and is either "common knowledge" or formally proven elsewhere. Some of the claims are intuitions based on experience with algorithms, and in a more formal setting should be classified as conjectures.

Using an improved backtrack algorithm with sophisticated pruning techniques, we revise previous observations correlating a high frequency of hard to solve Hamiltonian Cycle instances with the Gn,m phase transition between Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500 vertices are easily solved. When we artificially restrict the degree sequence with a bounded maximum degree, although there is some increase in difficulty, the frequency of hard graphs is still low. When we consider more regular graphs based on a generalization of knight's tours, we observe frequent instances of really hard graphs, but on these the average degree is bounded by a constant. We design a set of graphs with a feature our algorithm is unable to detect and so are very hard for our algorithm, but in these we can vary the average degree from O(1) to O(n). We have so far found no class of graphs correlated with the Gn,m phase transition which asymptotically produces a high frequency of hard instances.

Abstract In this paper, we consider the integral multicommodity flow problem on directed graphs underlying two classes of multistage interconnection networks. In one direction, we consider three‐stage networks. Using existing results on (g, f)‐factors of bipartite graphs, we show sufficient and necessary conditions for the existence of a solution when the network has at most two secondary switches. In contrast, the problem is shown to be NP‐complete if the network has three or more secondaries. In a second direction, we introduce a recursive class of networks that includes multistage hypercubic networks (such as the omega network, the indirect binary n‐cube, and the generalized cube network) as a proper subset. Networks in the new class may have an arbitrary number of stages. Moreover, each stage may contain identical switches of any arbitrary size. The notion of extrastage networks is extended to the new class, and the problem is shown to have polynomial time solutions on r‐stage networks where r = 3 or where each link has a unit capacity and r ≥ 3. The latter result implies an efficient algorithm for deciding admissible permutations on conventional extrastage hypercubic networks. In contrast, we show that the multicommodity flow problem is NP‐complete on extrastage networks, even if r = 6, each link has an integral capacity ≤ 3, and all flow demands are equal.

We compare the search power of crossover and mutation in genetic algorithms. Our discussion is framed within a model of computation using search space structures induced by these operators. Isomorphisms between the search spaces generated by these operators on small populations are identified and explored. These are closely related to the binary reflected Gray code. Using these we generate discriminating functions that are hard for one operator but easy for the other and show how to transform from one case to the other. We use these functions to provide theoretical evidence that traditional GAs use mutation more effectively than crossover, but dispute claims that mutation is a better search mechanism than crossover. To the contrary, we show that methods that exploit crossover more effectively can be designed and give evidence that these are powerful search mechanisms. Experimental results using GIGA, the Gene Invariant Genetic Algorithm, and the well-known GENESIS program support these theoretical claims. Finally, this paper provides the initial approach to a different method of analysis of GAs that does not depend on schema analysis or the notions of increased allocations of trials to hyperplanes of above-average fitness. Instead it focuses on the search space structure induced by the operators and the effect of a population search using them.

In this paper we present an extensive study into the long-term behaviour of binary search trees subjected to updates using the usual deletion algorithms taught in introductory textbooks. We develop a model of the behaviour of such trees which leads us to conjecture that the asymptotic average search path length is Θ(N½). We present results of large simulations which strongly support this conjecture. However, introducing a simple modification to ensure symmetry in the algorithms, the model predicts no such long-term deterioration. Simulations in fact indicate that asymptotically the average path length of such trees is less than the 1.386…log2 N average path length of trees generated from random insertion sequences.

It is shown that the following minimum cover problems are NP-hard, even for polygons without holes: (1) covering an arbitrary polygon with convex polygons; (2) covering the boundary of an arbitrary polygon with convex polygons; (3) covering an orthogonal polygon with rectangles; and (4) covering the boundary of an orthogonal polygon with rectangles. It is noted that these results hold even if the polygons are required to be in general position.>

The problem of covering a polygon with convex polygons has proven to be very difficult, even when restricted to the class of orthogonal polygons using orthogonally convex covers. We develop a method of analysis based on dent diagrams for orthogonal polygons, and are able to show that Keil's Ο(n2) algorithm for covering horizontally convex polygons is optimal, but can be improved to Ο(n) for counting the number of polygons required for a minimal cover. We also give an optimal Ο(n2) algorithm for covering another subclass of orthogonal polygons. Finally, we develop a method of signatures which can be used to obtain polynomial time algorithms for an even larger class of orthogonal polygons.

In this paper we present an algorithm to create simple polygons with a particular sequence of exterior angles, given only the sequence of angles. The algorithm has worst case time complexity Ο(Dn), where n is the number of angles and D is dependent on the angles. As a bonus, the algorithm proves an interesting converse of the ancient theorem that the sum of the exterior angles of a simple polygon is 2π radians.

If a binary search tree is created by inserting N keys in random order using the usual insertion algorithm, then it is well known that the average search path is about 1.4lgN. However, if deletions, using the frequently recommended Hibbard's algorithm, are interspersed with the insertions, then virtually nothing has been proven except for Knuth and Jonassen's very difficult, but complete, analysis of the case N = 3. In this paper it is shown that after a sufficient number of updates the average search path is θ(N1/2). An improved algorithm given by Knuth is shown to have the same asymptotic behavior.