Search

Database migration is a ubiquitous need faced by enterprises that generate and use vast amounts of data. This is because of database software updates, or it is from changes to hardware, project standards, and other business factors. Migrating a large collection of databases is a way more challenging task than migrating a single database because of the presence of additional constraints. These constraints include capacities of shifts and sizes of databases. In this paper, we present a comprehensive framework that can be used to model database migration problems of different enterprises with customized constraints by appropriately instantiating the parameters of the framework. These parameters are the size of each database, the size of each shift, and the cost of testing each application. Each of these parameters can be either constant or arbitrary. Additionally, the cost of testing an application can be proportional to the number of databases that the application uses. We establish the computational complexities of a number of instantiations of this framework. We present fixed -parameter intractability results for various relevant parameters of the database migration problem. We also provide approximability and inapproximability results as well as lower bounds for the running time of any exact algorithm for the database migration problem. We show that the database migration problem is equivalent to a variation of the classical hypergraph partitioning problem. Our theoretical results also imply new theoretical results for the hypergraph partitioning problem that are interesting in their own right. Finally, we adapt heuristic algorithms devised for the hypergraph partitioning problem to the database migration problem, and we also give experimental results for the adapted heuristics.

Article; Early Access, Database migration is an important problem faced by companies dealing with big data. Not only is migration a costly procedure, but it also involves serious security risks as well. For some institutions, the primary focus is on reducing the cost of the migration operation, which manifests itself in application testing. For other institutions, minimizing security risks is the most important goal, especially if the data involved is of a sensitive nature. In the literature, the database migration problem has been studied from a test cost minimization perspective. In this paper, we focus on an orthogonal measure, i.e., security risk minimization. We associate security with the number of shifts needed to complete the migration task. Ideally, we want to complete the migration in as few shifts as possible, so that the risk of data exposure is minimized. In this paper, we provide a formal framework for studying the database migration problem from the perspective of security risk minimization (shift minimization) and establish the computational complexities of several models in the same. For the NP-hard models, we develop memetic algorithms that produce solutions that are within 10% and 7% of the optimal in 95% of the instances under 8 and 82 seconds, respectively., Defense Advanced Research Projects Agency [HR001123S0001-FP-004], AcknowledgementsThis research was supported in part by the Defense Advanced Research Projects Agency through grant HR001123S0001-FP-004.

This paper is concerned with a new variant of bin packing called priority-based bin packing with subset constraints (PBBP-SC). PBBP-SC is a variant of traditional bin packing (TBP). In a TBP instance, we are given a collection of items {t1,t2,…tn}, where each item ti has size si∈(0,1). The goal of TBP is to pack the items in as few unit-sized bins as possible. In a PBBP-SC instance, we are given a collection of n unit-size items and a collection of m 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 being included 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. The first problem we study is the feasibility problem. This is the problem of checking if there is a feasible assignment to a given PBBP-SC instance. The second problem we study is the priority maximization problem. This is the problem of finding a maximum priority assignment of an infeasible PBBP-SC instance. The third problem we study is the bin minimization problem. This is the problem of finding an assignment with the fewest number of bins to pack all of the items in a feasible PBBP-SC instance. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems. In particular, we show that both the feasibility and priority maximization problems are solvable in polynomial time. We also show that the bin minimization problem is log-APX-complete and cannot be solved in time o(1.41m) unless the Strong Exponential Time Hypothesis fails. © 2023 Elsevier B.V., Defense Advanced Research Projects Agency, DARPA: HR001123S0001-FP-004, This research was supported in part by the Defense Advanced Research Projects Agency through grant HR001123S0001-FP-004 .

Article; Early Access, Database migration is an important problem faced by companies dealing with big data. Not only is migration a costly procedure, but it also involves serious security risks as well. For some institutions, the primary focus is on reducing the cost of the migration operation, which manifests itself in application testing. For other institutions, minimizing security risks is the most important goal, especially if the data involved is of a sensitive nature. In the literature, the database migration problem has been studied from a test cost minimization perspective. In this paper, we focus on an orthogonal measure, i.e., security risk minimization. We associate security with the number of shifts needed to complete the migration task. Ideally, we want to complete the migration in as few shifts as possible, so that the risk of data exposure is minimized. In this paper, we provide a formal framework for studying the database migration problem from the perspective of security risk minimization (shift minimization) and establish the computational complexities of several models in the same. For the NP-hard models, we develop memetic algorithms that produce solutions that are within 10% and 7% of the optimal in 95% of the instances under 8 and 82 seconds, respectively., Defense Advanced Research Projects Agency [HR001123S0001-FP-004], AcknowledgementsThis research was supported in part by the Defense Advanced Research Projects Agency through grant HR001123S0001-FP-004.

This paper is concerned with a new variant of bin packing called priority-based bin packing with subset constraints (PBBP-SC). PBBP-SC is a variant of traditional bin packing (TBP). In a TBP instance, we are given a collection of items {t1,t2,…tn}, where each item ti has size si∈(0,1). The goal of TBP is to pack the items in as few unit-sized bins as possible. In a PBBP-SC instance, we are given a collection of n unit-size items and a collection of m 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 being included 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. The first problem we study is the feasibility problem. This is the problem of checking if there is a feasible assignment to a given PBBP-SC instance. The second problem we study is the priority maximization problem. This is the problem of finding a maximum priority assignment of an infeasible PBBP-SC instance. The third problem we study is the bin minimization problem. This is the problem of finding an assignment with the fewest number of bins to pack all of the items in a feasible PBBP-SC instance. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems. In particular, we show that both the feasibility and priority maximization problems are solvable in polynomial time. We also show that the bin minimization problem is log-APX-complete and cannot be solved in time o(1.41m) unless the Strong Exponential Time Hypothesis fails. © 2023 Elsevier B.V., Defense Advanced Research Projects Agency, DARPA: HR001123S0001-FP-004, This research was supported in part by the Defense Advanced Research Projects Agency through grant HR001123S0001-FP-004 .

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.

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.

In this paper, we investigate properties of cutting plane based refutations for a class of integer programs called Horn constraint systems (HCS). Briefly, a system of linear inequalities A * x >= b is called a Horn constraint system, if each entry in A belongs to the set {0,1,-1} and furthermore there is at most one positive entry per row. Our focus is on deriving refutations i.e., proofs of unsatisfiability of such programs using cutting planes as a proof system. We also look at several properties of these refutations. Horn constraint systems can be considered as a more general form of propositional Horn formulas, i.e., CNF formulas with at most one positive literal per clause. Cutting plane calculus (CP) is a well-known calculus for deciding the unsatisfiability of propositional CNF formulas and integer programs. Usually, CP consists of a pair of inference rules. These are called the addition rule (ADD) and the division rule (DIV). In this paper, we show that cutting plane calculus is still complete for Horn constraints when every intermediate constraint is required to be Horn. We also investigate the lengths of cutting plane proofs for Horn constraint systems.

In this paper, we investigate properties of cutting plane based refutations for a class of integer programs called Horn constraint systems (HCS). Briefly, a system of linear inequalities A * x >= b is called a Horn constraint system, if each entry in A belongs to the set {0,1,-1} and furthermore there is at most one positive entry per row. Our focus is on deriving refutations i.e., proofs of unsatisfiability of such programs using cutting planes as a proof system. We also look at several properties of these refutations. Horn constraint systems can be considered as a more general form of propositional Horn formulas, i.e., CNF formulas with at most one positive literal per clause. Cutting plane calculus (CP) is a well-known calculus for deciding the unsatisfiability of propositional CNF formulas and integer programs. Usually, CP consists of a pair of inference rules. These are called the addition rule (ADD) and the division rule (DIV). In this paper, we show that cutting plane calculus is still complete for Horn constraints when every intermediate constraint is required to be Horn. We also investigate the lengths of cutting plane proofs for Horn constraint systems.

In the weighted partial vertex cover problem (WPVC), we are given a graph $G=(V,E)$, cost function $c:V\rightarrow N$, profit function $p:E\rightarrow N$, and positive integers $R$ and $L$. The goal is to check whether there is a subset $V'\subseteq V$ of cost at most $R$, such that the total profit of edges covered by $V'$ is at least $L$. In this paper we study the fixed-parameter tractability of WPVC in bipartite graphs (WPVCB). By extending the methods of Amini et al., we show that WPVCB is FPT with respect to $R$ if $c\equiv 1$. On the negative side, it is $W[1]$-hard for arbitrary $c$, even when $p\equiv 1$. In particular, WPVCB is $W[1]$-hard parameterized by $R$. We complement this negative result by proving that for bounded-degree graphs WPVC is FPT with respect to $R$. The same result holds for the case of WPVCB when we allow to take only one fractional vertex. Additionally, we show that WPVC is FPT with respect to $L$. Finally, we discuss a variant of PVCB in which the edges covered are constrained to include a matching of prescribed size and derive a paramterized algorithm for the same., Comment: 12 pages, no figures

In this paper, we analyze 2CNF formulas from the perspectives of Read-Once resolution (ROR) refutation schemes. We focus on two types of ROR refutations, viz., variable-once refutation and clause-once refutation. In the former, each variable may be used at most once in the derivation of a refutation, while in the latter, each clause may be used at most once. We show that the problem of checking whether a given 2CNF formula has an ROR refutation under both schemes is NP-complete. This is surprising in light of the fact that there exist polynomial refutation schemes (tree-resolution and DAG-resolution) for 2CNF formulas. On the positive side, we show that 2CNF formulas have copy-complexity 2, which means that any unsatisfiable 2CNF formula has a refutation in which any clause needs to be used at most twice., Comment: 14 pages, 3 figures

The Shoshan-Zwick algorithm solves the all pairs shortest paths problem in undirected graphs with integer edge costs in the range $\{1, 2, \dots, M\}$. It runs in $\tilde{O}(M\cdot n^{\omega})$ time, where $n$ is the number of vertices, $M$ is the largest integer edge cost, and $\omega < 2.3727$ is the exponent of matrix multiplication. It is the fastest known algorithm for this problem. This paper points out the erroneous behavior of the Shoshan-Zwick algorithm and revises the algorithm to resolve the issues that cause this behavior. Moreover, it discusses implementation aspects of the Shoshan-Zwick algorithm using currently-existing sub-cubic matrix multiplication algorithms., Comment: 16 pages

Parameter variability and the existence of complex constraints between tasks are assured features of real-time scheduling. {\em Periodicity} of task sets is an additional feature that needs to be accomodated. Traditional scheduling models ignore the complexities involved in real-time scheduling by making simplistic assumptions about task interactions. In this paper, we present a model that captures the issues that we deem central to real-time scheduling in periodic task sets and demonstrate the existence of efficient and easily implementable algorithms for addressing schedulability queries in this model. Our model is very general and applicable to diverse areas ranging from real-time process scheduling in operating systems and avionics to manufacturing and traffic control. (Also cross-referenced as UMIACS-TR-2000-25)

Parameter variability and the existence of complex constraints between tasks are assured features of real-time scheduling. {\em Periodicity} of task sets is an additional feature that needs to be accomodated. Traditional scheduling models ignore the complexities involved in real-time scheduling by making simplistic assumptions about task interactions. In this paper, we present a model that captures the issues that we deem central to real-time scheduling in periodic task sets and demonstrate the existence of efficient and easily implementable algorithms for addressing schedulability queries in this model. Our model is very general and applicable to diverse areas ranging from real-time process scheduling in operating systems and avionics to manufacturing and traffic control. (Also cross-referenced as UMIACS-TR-2000-25)

The problem of parametric scheduling in hard real-time systems, ( in the presence of linear relative constraints between the start and execution times of tasks ) was posed in the litreature. In an earlier paper, a polynomial time algorithm is presented for the case when the constraints are restricted to be standard ( defined in paper ) and the execution time vectors belong to an axis-parallel hyper-rectangle. In this paper, we extend their results in two directions. We first present a polynomial time algorithm for the case when the execution time vectors belong to arbitrary convex domains. We then show that the set of standard constraints can be extended to include arbitrary network constraints. Our insights into the problem occur primarily as a result of studying the dual polytope of the constraint system. (Also cross-refernced as UMIACS-TR-2000-11)

In the design of real-time systems, it is often the case that certain process parameters ( such as {\em execution time} ) are not known precisely. The challenge in real-time system design is to develop techniques that efficiently meet the requirements of impreciseness. Traditional models tend to simplify the issue of impreciseness by assuming {\em worst-case} times. This assumption is unrealistic and at the same time, may cause certain constraints to be violated at run-time. In this paper, we shall study the problem of scheduling a set of ordered, non-preemptive processes under non-constant execution times. Typical applications for variable execution time scheduling include process scheduling in Real-time Operating Systems such as Maruti, compiler scheduling, database transaction scheduling and automated machine control. An important feature of application areas such as robotics is the interaction between execution times of various processes. We explicitly model this interaction through the representation of execution time vectors as points in convex sets. We present both sequential and parallel algorithms for determining the existence of a static schedule. (Also cross-referenced as UMIACS-TR-2000-14)

Parameter variability and the existence of complex constraints between tasks are assured features of real-time scheduling. {\em Periodicity} of task sets is an additional feature that needs to be accomodated. Traditional scheduling models ignore the complexities involved in real-time scheduling by making simplistic assumptions about task interactions. In this paper, we present a model that captures the issues that we deem central to real-time scheduling in periodic task sets and demonstrate the existence of efficient and easily implementable algorithms for addressing schedulability queries in this model. Our model is very general and applicable to diverse areas ranging from real-time process scheduling in operating systems and avionics to manufacturing and traffic control. (Also cross-referenced as UMIACS-TR-2000-25)

The problem of parametric scheduling in hard real-time systems, ( in the presence of linear relative constraints between the start and execution times of tasks ) was posed in the litreature. In an earlier paper, a polynomial time algorithm is presented for the case when the constraints are restricted to be standard ( defined in paper ) and the execution time vectors belong to an axis-parallel hyper-rectangle. In this paper, we extend their results in two directions. We first present a polynomial time algorithm for the case when the execution time vectors belong to arbitrary convex domains. We then show that the set of standard constraints can be extended to include arbitrary network constraints. Our insights into the problem occur primarily as a result of studying the dual polytope of the constraint system. (Also cross-refernced as UMIACS-TR-2000-11)

In the design of real-time systems, it is often the case that certain process parameters ( such as {\em execution time} ) are not known precisely. The challenge in real-time system design is to develop techniques that efficiently meet the requirements of impreciseness. Traditional models tend to simplify the issue of impreciseness by assuming {\em worst-case} times. This assumption is unrealistic and at the same time, may cause certain constraints to be violated at run-time. In this paper, we shall study the problem of scheduling a set of ordered, non-preemptive processes under non-constant execution times. Typical applications for variable execution time scheduling include process scheduling in Real-time Operating Systems such as Maruti, compiler scheduling, database transaction scheduling and automated machine control. An important feature of application areas such as robotics is the interaction between execution times of various processes. We explicitly model this interaction through the representation of execution time vectors as points in convex sets. We present both sequential and parallel algorithms for determining the existence of a static schedule. (Also cross-referenced as UMIACS-TR-2000-14)

In the design of real-time systems, it is often the case that certain process parameters ( such as {\em execution time} ) are not known precisely. The challenge in real-time system design is to develop techniques that efficiently meet the requirements of impreciseness. Traditional models tend to simplify the issue of impreciseness by assuming {\em worst-case} times. This assumption is unrealistic and at the same time, may cause certain constraints to be violated at run-time. In this paper, we shall study the problem of scheduling a set of ordered, non-preemptive processes under non-constant execution times. Typical applications for variable execution time scheduling include process scheduling in Real-time Operating Systems such as Maruti, compiler scheduling, database transaction scheduling and automated machine control. An important feature of application areas such as robotics is the interaction between execution times of various processes. We explicitly model this interaction through the representation of execution time vectors as points in convex sets. We present both sequential and parallel algorithms for determining the existence of a static schedule. (Also cross-referenced as UMIACS-TR-2000-14)

The problem of parametric scheduling in hard real-time systems, ( in the presence of linear relative constraints between the start and execution times of tasks ) was posed in the litreature. In an earlier paper, a polynomial time algorithm is presented for the case when the constraints are restricted to be standard ( defined in paper ) and the execution time vectors belong to an axis-parallel hyper-rectangle. In this paper, we extend their results in two directions. We first present a polynomial time algorithm for the case when the execution time vectors belong to arbitrary convex domains. We then show that the set of standard constraints can be extended to include arbitrary network constraints. Our insights into the problem occur primarily as a result of studying the dual polytope of the constraint system. (Also cross-refernced as UMIACS-TR-2000-11)

The modern integrated circuit is one of the most complex products that has been engineered to-date. It continues to grow in complexity as the years progress. As a result, very large-scale integrated (VLSI) circuit design now involves massive design teams employing state-of-the art computer-aided design (CAD) tools. One of the oldest, yet most important CAD problems for VLSI circuits is physical design automation, where one needs to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface \cite{Lim08}. The process of mapping an electronic design to a chip involves a number of physical design stages, one of which is clustering. In this paper, we focus on problems in clustering which are critical for more sustainable chips. The clustering problem in combinatorial circuits alone is a source of multiple models. In particular, we consider the problem of clustering combinatorial circuits for delay minimization, when logic replication is not allowed ({\sc CN}). The problem of delay minimization when logic replication is allowed ({\sc CA}) has been well studied, and is known to be solvable in polynomial-time \cite{Wong1}. However, unbounded logic replication can be quite expensive. Thus, {\sc CN} is an important problem. We show that selected variants of {\sc CN} are {\bf NP-hard}. We also obtain approximability and inapproximability results for these problems. A preliminary version of this paper appeared in \cite{Don15}., Comment: 20 pages, 10 figures

Saliva as a biological fluid is gaining wider acceptance for diagnosing diseases. The growing interest in saliva as a biological fluid is due to its noninvasiveness, ease of use, cost-effectiveness, and multiple sample collection possibilities as well as minimal risk to health care professionals of contracting infectious organisms such as HIV and Hep B. However, the clinical translation of saliva is hampered by our lack of understanding of the biomolecular transportation from blood into saliva, the diurnal variations of biomolecules present in saliva, and relatively low levels of analytes (100th to a 1000th fold less than in blood). We provide information on the current status of salivary research, salivary diagnostics empowered by nanotechnology, and future prospects in this emerging field of saliva diagnostics.

It is well-known that the Vertex Cover problem is in P on bipartite graphs, however; the computational complexity of the Partial Vertex Cover problem on bipartite graphs is open. In this paper, we first show that the Partial Vertex Cover problem is NP-hard on bipartite graphs. We then identify an interesting special case of bipartite graphs, for which the Partial Vertex Cover problem can be solved in polynomial-time. We also show that the set of acyclic bipartite graphs, i.e., forests, and the set of bipartite graph where the degree of each vertex is at most 3 fall into that special case. Therefore, we prove that the Partial Vertex Cover problem is in P on trees, and it is also in P on the set of bipartite graphs where the degree of each vertex is at most 3., Comment: 11 pages, 4 figures

In this paper, we propose an efficient method for implementing Dijkstra's algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge lengths. The SSSPP is one of the most widely studied problems in theoretical computer science and operations research. On a graph with n vertices, m edges and K distinct edge lengths, our algorithm runs in O(m) time if nK=<2m, and O(mlognKm) time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths., United States. Dept. of Energy. Office of Science (contract DE-AC02-05CH11231), United States. Air Force Office of Scientific Research (grant FA9550-06-1-0050), National Science Foundation (U.S.) (award CCF-0827397)

Objectives: The aim of the present study was to compare a newly developed biodegradable polylactide/polyglycolide/N-methyl-2-pyrrolidone (PLGA/NMP) membrane with a standard resorbable collagen membrane (RCM) in combination with and without the use of a bone substitute material (deproteinized bovine bone mineral [DBBM]) looking at the proposed tenting effect and bone regeneration. Materials and methods: In five adult German sheepdogs, the mandibular premolars P2, P3, P4, and the molar M1 were bilaterally extracted creating two bony defects on each site. A total of 20 dental implants were inserted and allocated to four different treatment modalities within each dog: PLGA/NMP membrane only (Test 1), PLGA/NMP membrane with DBBM (Test 2), RCM only (negative control), and RCM with DBBM (positive control). A histomorphometric analysis was performed 12 weeks after implantation. For statistical analysis, a Friedman test and subsequently a Wilcoxon signed ranks test were applied. Results: In four out of five PLGA/NMP membrane-treated defects, the membranes had broken into pieces without the support of DBBM. This led to a worse outcome than in the RCM group. In combination with DBBM, both membranes revealed similar amounts of area of bone regeneration and bone-to-implant contact without significant differences. On the level of the third implant thread, the PLGA/NMP membrane induced more horizontal bone formation beyond the graft than the RCM. Conclusion: The newly developed PLGA/NMP membrane performs equally well as the RCM when applied in combination with DBBM. Without bone substitute material, the PLGA/NMP membrane performed worse than the RCM in challenging defects, and therefore, a combination with a bone substitute material is recommended. To cite this article: Jung RE, Kokovic V, Jurisic M, Yaman D, Subramani K, Weber FE. Guided bone regeneration with a synthetic biodegradable membrane: a comparative study in dogs. Clin. Oral Impl. Res. xx, 2010; 000-000.

In this report we summarize our contributions over the period 2006-2010. The principal objective of our work is the design, development and analysis of fundamentally new techniques for the problem of solving conjunctions of difference constraints. This problem is well-known to be equivalent to the problem of checking whether a directed graph (network) with positive and negative weights on its edges has a negative cost cycle (NCCD). The NCCD problem finds applications in a number of different design domains such as Program Verification, Real-Time Scheduling and Operations Research. We have looked at several variants of the NCCD problem, including the lightest negative cycle problem, the Horn constraint problem and the Unit Two Variable Per Inequality constraint problem. Each of the specialized constraint classes Our work has resulted in numerous publications in respected journals and conferences., The original document contains color images.

We consider the satisfiability problem for Boolean combinations of generalized 2 SAT constraints, which are linear constraints with at most two, possibly unbounded, integer variables having coefficients in {-1,1}.

Traditional scheduling models assume that the execution time of a job in a periodic job-set is constant in every instance of it execution. This assumption does not hold in real-time systems wherein job execution time is known to vary. A second feature of traditional models is their lack of expressiveness, in that constraints more complex than precedence constraints (for instance, relative timing constraints) cannot be modeled. Thirdly, the schedulability of a real-time system depends upon the degree of clairvoyance afforded to the dispatcher. In this paper, we shall discuss Totally Clairvoyant Scheduling, as modeled within the E-T-C scheduling framework. We show that instantiation of the scheduling framework captures the central issues in a real-time flow-shop scheduling problem and design a polynomial time sequential algorithm for the same. We also introduce an error-minimizing performance metric called Violation Degree and establish that optimizing this metric in a Totally Clairvoyant Scheduling System in NP-Hard.

This chapter provides an overview of nanotechnology and its future applications in dentistry. In the field of medicine, nanotechnology has been applied in diagnosis, prevention, and treatment of diseases. Nanotechnology offers considerable scope in dentistry to improve dental treatment, care, and prevention of oral diseases. Nanotechnology has been in dentistry for tooth sealants and fillers that use nanosized particles to improve their strength, luster, and resist wear. Antimicrobial nanoparticles in restorative composite materials are used to prevent dental caries. Silver particles as antibacterial agents when used in fillers and toothpastes can retard bacterial growth and reduce tooth decay. It is envisaged that in the longer term biomimetic approaches and nanotechnology will be used to repair and rebuild damaged enamel. In near future, nanomaterials will be used far more widely and will yield superior properties and combined with biotechnology, laser and digital guided surgery will provide excellent dental care. Smarter preventive measures and earlier interventions to avert craniofacial disorders using nanodiagnostics seems a reality. Nanotechnology research will pave the way for development of tools which would allow clinicians to diagnose and treat oral malignancies at their earliest stage. © 2012 Elsevier Inc. All rights reserved.