Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

A dual-slope analogue-to-digital converter for generating polynomials

A new digital polynomial generator using the principle of dual-slope analogue-to-digital conversion is proposed. Techniques for realizing a wide range of integer as well as fractional coefficients to obtain the desired polynomial have been discussed. The suitability of realizing the proposed polynomial generator in integrated circuit form is also indicated.

Non-linear and linear postulations of technology adoption determinants

Using polynomial regression and response surface analysis to examine the non-linearity between variables, this study demonstrates that better analytical nuances are required to investigate the relationships between constructs when the underlying theories suggest non-linearity. By utilising the Theory of Planned Behaviour (TPB), Ettlie’s adoption stages as well as employing data gathered from 162 owners of Small and Medium-sized Enterprises (SMEs), our findings reveal that subjective norms and attitude have differing influences upon behavioural intention in both the evaluation and trial stages of the adoption.

Identification of a class of non-linear systems

This paper considers the on-line identification of a non-linear system in terms of a Hammerstein model, with a zero-memory non-linear gain followed by a linear system. The linear part is represented by a Laguerre expansion of its impulse response and the non-linear part by a polynomial. The identification procedure involves determination of the coefficients of the Laguerre expansion of correlation functions and an iterative adjustment of the parameters of the non-linear gain by gradient methods. The method is applicable to situations involving a wide class of input signals. Even in the presence of additive correlated noise, satisfactory performance is achieved with the variance of the error converging to a value close to the variance of the noise. Digital computer simulation establishes the practicability of the scheme in different situations.

The transient response of certain third-ordernon-linear systems

In this paper a method of solving certain third-order non-linear systems by using themethod of ultraspherical polynomial approximation is proposed. By using the method of variation of parameters the third-order equation is reduced to three partial differential equations. Instead of being averaged over a cycle, the non-linear functions are expanded in ultraspherical polynomials and with only the constant term retained, the equations are solved. The results of the procedure are compared with the numerical solutions obtained on a digital computer. A degenerate third-order system is also considered and results obtained for the above system are compared with numerical results obtained on the digital computer. There is good agreement between the results obtained by the proposed method and the numerical solution obtained on digital computer.

The dynamic stability of degenerate systems under parametric excitation

The parametric resonance in a system having two modes of the same frequency is studied. The simultaneous occurence of the instabilities of the first and second kind is examined, by using a generalized perturbation procedure. The region of instability in the first approximation is obtained by using the Sturm's theorem for the roots of a polynomial equation.

Self-tuning minimum-variance control of nonlinear systems of the Hammerstein model

Self-tuning is applied to the control of nonlinear systems represented by the Hammerstein model wherein the nonlinearity is any odd-order polynomial. But control costing is not feasible in general. Initial relay control is employed to contain the deviations.

Conformal Field Theory Methods for Variants of Schramm-Loewner Evolutions

This thesis consists of an introduction, four research articles and an appendix. The thesis studies relations between two different approaches to continuum limit of models of two dimensional statistical mechanics at criticality. The approach of conformal field theory (CFT) could be thought of as the algebraic classification of some basic objects in these models. It has been succesfully used by physicists since 1980's. The other approach, Schramm-Loewner evolutions (SLEs), is a recently introduced set of mathematical methods to study random curves or interfaces occurring in the continuum limit of the models. The first and second included articles argue on basis of statistical mechanics what would be a plausible relation between SLEs and conformal field theory. The first article studies multiple SLEs, several random curves simultaneously in a domain. The proposed definition is compatible with a natural commutation requirement suggested by Dubédat. The curves of multiple SLE may form different topological configurations, ``pure geometries''. We conjecture a relation between the topological configurations and CFT concepts of conformal blocks and operator product expansions. Example applications of multiple SLEs include crossing probabilities for percolation and Ising model. The second article studies SLE variants that represent models with boundary conditions implemented by primary fields. The most well known of these, SLE(kappa, rho), is shown to be simple in terms of the Coulomb gas formalism of CFT. In the third article the space of local martingales for variants of SLE is shown to carry a representation of Virasoro algebra. Finding this structure is guided by the relation of SLEs and CFTs in general, but the result is established in a straightforward fashion. This article, too, emphasizes multiple SLEs and proposes a possible way of treating pure geometries in terms of Coulomb gas. The fourth article states results of applications of the Virasoro structure to the open questions of SLE reversibility and duality. Proofs of the stated results are provided in the appendix. The objective is an indirect computation of certain polynomial expected values. Provided that these expected values exist, in generic cases they are shown to possess the desired properties, thus giving support for both reversibility and duality.

Homoclinic Splitting without Trees

We study a Hamiltonian describing a pendulum coupled with several anisochronous oscillators, giving a simple construction of unstable KAM tori and their stable and unstable manifolds for analytic perturbations. When the coupling takes place through an even trigonometric polynomial in the angle variables, we extend analytically the solutions of the equations of motion, order by order in the perturbation parameter, to a large neighbourhood of the real line representing time. Subsequently, we devise an asymptotic expansion for the splitting (matrix) associated with a homoclinic point. This expansion consists of contributions that are manifestly exponentially small in the limit of vanishing gravity, by a shift-of-countour argument. Hence, we infer a similar upper bound for the splitting itself. In particular, the derivation of the result does not call for a tree expansion with explicit cancellation mechanisms.

On Random Planar Curves and Their Scaling Limits

Planar curves arise naturally as interfaces between two regions of the plane. An important part of statistical physics is the study of lattice models. This thesis is about the interfaces of 2D lattice models. The scaling limit is an infinite system limit which is taken by letting the lattice mesh decrease to zero. At criticality, the scaling limit of an interface is one of the SLE curves (Schramm-Loewner evolution), introduced by Oded Schramm. This family of random curves is parametrized by a real variable, which determines the universality class of the model. The first and the second paper of this thesis study properties of SLEs. They contain two different methods to study the whole SLE curve, which is, in fact, the most interesting object from the statistical physics point of view. These methods are applied to study two symmetries of SLE: reversibility and duality. The first paper uses an algebraic method and a representation of the Virasoro algebra to find common martingales to different processes, and that way, to confirm the symmetries for polynomial expected values of natural SLE data. In the second paper, a recursion is obtained for the same kind of expected values. The recursion is based on stationarity of the law of the whole SLE curve under a SLE induced flow. The third paper deals with one of the most central questions of the field and provides a framework of estimates for describing 2D scaling limits by SLE curves. In particular, it is shown that a weak estimate on the probability of an annulus crossing implies that a random curve arising from a statistical physics model will have scaling limits and those will be well-described by Loewner evolutions with random driving forces.

Application of ultraspherical polynomials to forced oscillations of a third-order non-linear system

In this paper the method of ultraspherical polynomial approximation is applied to study the steady-state response in forced oscillations of a third-order non-linear system. The non-linear function is expanded in ultraspherical polynomials and the expansion is restricted to the linear term. The equation for the response curve is obtained by using the linearized equation and the results are presented graphically. The agreement between the approximate solution and the analog computer solution is satisfactory. The problem of stability is not dealt with in this paper.

Problems and Algorithms for Sequence Segmentations

The analysis of sequential data is required in many diverse areas such as telecommunications, stock market analysis, and bioinformatics. A basic problem related to the analysis of sequential data is the sequence segmentation problem. A sequence segmentation is a partition of the sequence into a number of non-overlapping segments that cover all data points, such that each segment is as homogeneous as possible. This problem can be solved optimally using a standard dynamic programming algorithm. In the first part of the thesis, we present a new approximation algorithm for the sequence segmentation problem. This algorithm has smaller running time than the optimal dynamic programming algorithm, while it has bounded approximation ratio. The basic idea is to divide the input sequence into subsequences, solve the problem optimally in each subsequence, and then appropriately combine the solutions to the subproblems into one final solution. In the second part of the thesis, we study alternative segmentation models that are devised to better fit the data. More specifically, we focus on clustered segmentations and segmentations with rearrangements. While in the standard segmentation of a multidimensional sequence all dimensions share the same segment boundaries, in a clustered segmentation the multidimensional sequence is segmented in such a way that dimensions are allowed to form clusters. Each cluster of dimensions is then segmented separately. We formally define the problem of clustered segmentations and we experimentally show that segmenting sequences using this segmentation model, leads to solutions with smaller error for the same model cost. Segmentation with rearrangements is a novel variation to the segmentation problem: in addition to partitioning the sequence we also seek to apply a limited amount of reordering, so that the overall representation error is minimized. We formulate the problem of segmentation with rearrangements and we show that it is an NP-hard problem to solve or even to approximate. We devise effective algorithms for the proposed problem, combining ideas from dynamic programming and outlier detection algorithms in sequences. In the final part of the thesis, we discuss the problem of aggregating results of segmentation algorithms on the same set of data points. In this case, we are interested in producing a partitioning of the data that agrees as much as possible with the input partitions. We show that this problem can be solved optimally in polynomial time using dynamic programming. Furthermore, we show that not all data points are candidates for segment boundaries in the optimal solution.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

A new type of high-order elements based on the mesh-free interpolations

We propose a new type of high-order elements that incorporates the mesh-free Galerkin formulations into the framework of finite element method. Traditional polynomial interpolation is replaced by mesh-free interpolations in the present high-order elements, and the strain smoothing technique is used for integration of the governing equations based on smoothing cells. The properties of high-order elements, which are influenced by the basis function of mesh-free interpolations and boundary nodes, are discussed through numerical examples. It can be found that the basis function has significant influence on the computational accuracy and upper-lower bounds of energy norm, when the strain smoothing technique retains the softening phenomenon. This new type of high-order elements shows good performance when quadratic basis functions are used in the mesh-free interpolations and present elements prove advantageous in adaptive mesh and nodes refinement schemes. Furthermore, it shows less sensitive to the quality of element because it uses the mesh-free interpolations and obeys the Weakened Weak (W2) formulation as introduced in [3, 5].

Transient response of coupled non-linear non-conservative systems

This paper deals with an approximate method of analysis of non-linear, non-conservative systems of two degrees of freedom. The approximate equations for amplitude and phase are obtained by a generalized averaging technique based on the ultraspherical polynomial approximation. The method is illustrated by an example of a spring-mass-damper system.