In a nonparametric setting, the functional form of the relationship between the response variable and the associated predictor variables is unspecified; however it is assumed to be a smooth function. The main aim of nonparametric regression is to highlight an important structure in data without any assumptions about the shape of an underlying regression function. In regression, the random and fixed design models should be distinguished. Among the variety of nonparametric regression estimators currently in use, kernel type estimators are most popular. Kernel type estimators provide a flexible class of nonparametric procedures by estimating unknown function as a weighted average using a kernel function. The bandwidth which determines the influence of the kernel has to be adapted to any kernel type estimator. Our focus is on Nadaraya-Watson estimator and Local Linear estimator which belong to a class of kernel type regression estimators called local polynomial kerne l estimators. A closely related problem is the determination of an appropriate sample size that would be required to achieve a desired confidence level of accuracy for the nonparametric regression estimators. Since sequential procedures allow an experimenter to make decisions based on the smallest number of observations without compromising accuracy, application of sequential procedures to a nonparametric regression model at a given point or series of points is considered. The motivation for using such procedures is: in many applications the quality of estimating an underlying regression function in a controlled experiment is paramount; thus, it is reasonable to invoke a sequential procedure of estimation that chooses a sample size based on recorded observations that guarantees a preassigned accuracy. We have employed sequential techniques to develop a procedure for constructing a fixed-width confidence interval for the predicted value at a specific point of the independent variable. These fixed-width confidence intervals are developed using asymptotic properties of both Nadaraya-Watson and local linear kernel estimators of nonparametric kernel regression with data-driven bandwidths and studied for both fixed and random design contexts. The sample sizes for a preset confidence coefficient are optimized using sequential procedures, namely two-stage procedure, modified two-stage procedure and purely sequential procedure. The proposed methodology is first tested by employing a large-scale simulation study. The performance of each kernel estimation method is assessed by comparing their coverage accuracy with corresponding preset confidence coefficients, proximity of computed sample sizes match up to optimal sample sizes and contrasting the estimated values obtained from the two nonparametric methods with act ual values at given series of design points of interest. We also employed the symmetric bootstrap method which is considered as an alternative method of estimating properties of unknown distributions. Resampling is done from a suitably estimated residual distribution and utilizes the percentiles of the approximate distribution to construct confidence intervals for the curve at a set of given design points. A methodology is developed for determining whether it is advantageous to use the symmetric bootstrap method to reduce the extent of oversampling that is normally known to plague Stein's two-stage sequential procedure. The procedure developed is validated using an extensive simulation study and we also explore the asymptotic properties of the relevant estimators. Finally, application of our proposed sequential nonparametric kernel regression methods are made to some problems in software reliability and finance.

Both the maximum agreement forest problem and the multicut on trees problem are NP-hard, thus cannot be solved efficiently if P /=NP. The maximum agreement forest problem was motivated in the study of evolution trees in bioinformatics, in which we are given two leaf-labeled trees and are asked to find a maximum forest that is a subgraph of both trees. The multicuton trees problem has applications in networks, in which we are given a forest and a set of pairs of termianls and are asked to find a cut that separates all pairs of terminals. We develop combinatorial and algorithmic techniques that lead to improved parameterized algorithms, approximation algorithms, and kernelization algorithms for these problems. For the maximum agreement forest problem, we proceed from the bottommost level of trees and extend solutions to whole trees. With this technique, we show that the maxi- mum agreement forest problem is fixed-parameterized tractable in general trees, resolving an open problem in this area. We also provide the first constant ratio approximation algorithm for the problem in general trees. For the multicut on trees problem, we take a new look at the problem through the eyes of vertex cover problem. This connection allows us to develop an kernelization algorithm for the problem, which gives an upper bound of O(k3) on the kernel size, significantly improving the previous best upper bound O(k6). We further exploit this connection to give a parameterized algorithm for the problem that runs in time O∗ (1.62k), thus improving the previous best algorithm of running time O∗ (2k). In the protein complex prediction problem, which comes directly from the study of bioinformatics, we are given a protein-protein interaction network, and are asked to find dense regions in this graph. We formulate this problem as a graph clustering problem and develop an algorithm to refine the results for identifying protein complexes. We test our algorithm on yeast protein- protein interaction networks, and we show that our algorithm is able to identify complexes more accurately than other existing algorithms.

No description available.

The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints. We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. The question is very well motivated by the problem of channel assignment in wireless networks. This problem is NP-hard for q ≥ 2, and has been well-studied from the point of view of approximation. This problem has not been studied in the parameterized context before. Hence as a next step, this thesis investigates the parameterized complexity of this problem where the standard parameter is the solution size. The main focus of the work is the special case of q=2 ,i.e. MAXIMUM EDGE 2-COLORING which is theoretically intricate and practically relevant in the wireless networks setting. We first show an exponential kernel for the MAXIMUM EDGE q-COLORING problem where q is a fixed constant and q ≥ 2.We do a more specific analysis for the kernel of the MAXIMUM EDGE 2-COLORING problem. The kernel obtained here is still exponential in size but is better than the kernel obtained for MAXIMUM EDGE q-COLORING problem in case of q=2. We then show a fixed parameter tractable algorithm for the MAXIMUM EDGE 2-COLORING problem with a running time of O*∗(kO(k)).We also show a fixed parameter tractable algorithm for the MAXIMUM EDGE q-COLORING problem with a running time of O∗(kO(qk) qO(k)). The fixed parameter tractability of the dual parametrization of the MAXIMUM EDGE 2-COLORING problem is established by arguing a linear vertex kernel for the problem. We also show that the MAXIMUM EDGE 2-COLORING problem remains hard on graphs where the maximum degree is a constant and also on graphs without cycles of length four. In both these cases, we obtain quadratic kernels. A closely related variant of the problem is the question of MAX EDGE{1,2-}COLORING. For this problem, the vertices in the input graph may have different qε,{1.2} values and the goal is to use at least k colors for the edge coloring of the graph such that every vertex sees at most q colors, where q is either one or two. We show that the MAX EDGE{1,2}-COLORING problem is W[1]-hard on graphs that have no cycles of length four.