Summary In this paper, we propose a simulation model to study real‐world replication workflows for cloud storage systems. With this model, we present three new methods to maximize the storage space usage during replica creation, and two novel QoS aware greedy algorithms for replica placement optimization. By using a simulation method, our algorithms are evaluated, through a comparison with the existing placement algorithms, to show that (i) a more evenly distributed replicas for a data set can be achieved by using round‐robin methods in replica creation phase and (ii) the two proposed greedy algorithms, namedGS_QoSandGS_QoS_C1, not only have more economical results than those from Chenet al., but also guarantee the QoS for clients. Copyright © 2016 John Wiley & Sons, Ltd.

This paper proposes a replication cost model and two greedy algorithms, named GS QoS and GS QoS C1, for replication placements in cloud-based storage systems. The model aims to minimize replication cost with full consideration of quality of user access to storage nodes. Our two algorithms employ a utility measurement to guide placement procedures. Our final experimental results show that 1) GS QoS outperforms GS QoS C1, 2) both algorithms have more economical results than those from existing greedy replica placement algorithm.

In a shared cluster facility scheduling of parallel jobs is an important factor that can affect the performance and turnaround time of the submitted jobs. To solve hard tree search problems, we have designed the Dynamic Moldable Tree Search (DMTS) framework. The DMTS framework allows existing serial tree search applications to run in parallel with very little development effort. The DMTS framework is designed to run on parallel computing infrastructures, including clusters, computational grids, and clouds. Target applications for the DMTS framework are hard tree search problems such as Boolean satisfiability (SAT) problems. SAT is amongst the most important problems in theoretical computer science. In this paper we present a parallel Dynamic Moldable SAT (DMSAT) solver. DMSAT runs on top of the DMTS framework. DMSAT is a parallel version of minis at, miniSat is one of the most widely used open source SAT solvers. We compare the performance of DMSAT with PMSAT and miniSat. Our experimental results show that the dynamic moldable model of DMSAT perform much better than the other SAT solvers. In SAT race competitions all those problems that are not solved by a SAT solver within 1200 seconds are marked as unsolvable. DMSAT is also able to solve hard SAT problems that were not solvable by miniSat in the past SAT races.

We study the problem of determining whether a manufactured disk of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of the manufactured object, compute the thinnest annulus whose outer (or inner, or median) radius is r and that contains all the probe points. Our algorithms run in O(nlogn) time.

Every convex polytope can be representedas the intersectionof a finiteset of halfspaccs and as theconvex hull of its vertices.Transforming from the halfspace (respectively vertex) to the vertex (respectively halfspace) representationis called vertex enumeration (respectivelyjhcet enumeration).An open questionis whetherthere is analgorithmfor thesetwoproblems(equivalentby geometric du- ality) thatis polynomial in theinputsize and theoutputsize.In this papr, we extend theknown polynomially solvable classes of polytopes by looking at thedual problems.The dud problem of a vertex (facet, respectively) enumerationproblem is the facet (vertex)enumerationproblem for the same polytope where theinputand output are simply interchanged.For a particularclass of polytopes and a fixed algorithm, one transformationmay be much easier than its dual.In this paper, we propose a new class of algorithmsthattake advantageof this phenomenon.Ltmely speaking,prinra14ual algorithmsuse a solution to the easy direction as an oracle to help solve the seemingly harddkection.

A convex polytope is the bounded intersection of finite set H of halfspaces. A classic theorem of convexity theory is that every convex polyhedron can be expressed as the convex hull of its set V of vertices. There are three closely related computational problems related to the two descriptions of a polytope. The vertex enumeration problem is to compute V from H. The convex hull problem it to compute H from V. The polytope verification problem is to decide whether a given vertex description and halfspace description define the same polytope. The first two problems are essentially equivalent under point/hyperplane duality. It is an open problem whether any of these problems can be solved in time polynomial in jHj + jVj. In this paper we describe hard polytopes for convex hull algorithms based on pivoting , those based on triangulation, and for some insertion algorithms. 1 Introduction Although the simplex method had long been regarded as a practical and efficient algorithm for linear...

A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Such polyhedra can be manufactured easily using two cast parts. Assuming that the cast parts are removed by a single translation each, it is shown that for a simple polyhedron with n vertices, castability can be decided in O(n2logn) time and linear space using a simple algorithm. Furthermore, a more complicated algorithm solves the problem in O(n3/2+ε) time and space, for any fixed ε>0. In the case where the cast parts are to be removed in opposite directions, a simple O(n2) time algorithm is presented. Finally, if the object is a convex polyhedron and the cast parts are to be removed in opposite directions, a simple O(nlog2n) algorithm is presented.