Search

6th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2021 -- 6 September 2021 through 7 September 2021 -- 269749, An important ubiquitous task in modern cloud systems is the migration of databases from one location to another. In practical settings, the databases are migrated in several shifts in order to meet the quality of service requirements of the end-users [18]. Once a batch of databases is migrated in a shift, the applications that depend on the databases on that shift are to be immediately tested [8]. Testing an application is a costly procedure [25] and the number of times an application is to be tested throughout the migration process varies greatly depending on the migration schedule. An interesting algorithmic challenge is to find a schedule that minimizes the total testing cost of all the applications. This problem, referred to as the capacity constrained database migration (CCDM) problem, is known to be NP-hard and fixed-parameter intractable for various relevant parameters [24]. In this paper, we provide new approximability and inapproximability results as well as new conditional lower bounds for the running time of any exact algorithm for the CCDM problem. Also, we adapt heuristic algorithms devised for the Hypergraph Partitioning problem to the CCDM problem and give extensive experimental results. © 2021, Springer Nature Switzerland AG.

7th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2021 -- 11 February 2021 through 13 February 2021 -- 253869, This paper is concerned with a new variant of Traditional Bin Packing (TBP) called Priority-Based Bin Packing with Subset Constraints (PBBP-SC). In a TBP instance, we are given a collection of items { a1, a2, … an}, with ai? (0, 1 ) and a collection of unit-size bins { B1, B2, …, Bm}. One problem associated with TBP is the bin minimization problem. The goal of this problem is to pack the items in as few bins as possible. In a PBBP-SC instance, we are given a collection of unit-size items and a collection of bins of varying capacities. Associated with each item is a positive integer which is called its priority. The priority of an item indicates its importance in a (possibly infeasible) packing. As with the traditional case, these items need to be packed in the fewest number of bins. What complicates the problem is the fact that each item can be assigned to only one of a select set of bins, i.e., the bins are not interchangeable. We investigate several problems associated with PBBP-SC. Checking if there is a feasible assignment to a given instance is one problem. Finding a maximum priority assignment in case of the instance being infeasible is another. Finding an assignment with the fewest number of bins to pack a feasible instance is a third. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems. © 2021, Springer Nature Switzerland AG., FA9550-19-1-0177; Air Force Research Laboratory, AFRL: FA8750-17-S-7007, This research is supported in part by the Air-Force of Scientific Research through Grant FA9550-19-1-0177 and in part by the Air-Force Research Laboratory, Rome through Contract FA8750-17-S-7007.

6th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2021 -- 6 September 2021 through 7 September 2021 -- 269749, An important ubiquitous task in modern cloud systems is the migration of databases from one location to another. In practical settings, the databases are migrated in several shifts in order to meet the quality of service requirements of the end-users [18]. Once a batch of databases is migrated in a shift, the applications that depend on the databases on that shift are to be immediately tested [8]. Testing an application is a costly procedure [25] and the number of times an application is to be tested throughout the migration process varies greatly depending on the migration schedule. An interesting algorithmic challenge is to find a schedule that minimizes the total testing cost of all the applications. This problem, referred to as the capacity constrained database migration (CCDM) problem, is known to be NP-hard and fixed-parameter intractable for various relevant parameters [24]. In this paper, we provide new approximability and inapproximability results as well as new conditional lower bounds for the running time of any exact algorithm for the CCDM problem. Also, we adapt heuristic algorithms devised for the Hypergraph Partitioning problem to the CCDM problem and give extensive experimental results. © 2021, Springer Nature Switzerland AG.