Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

A Direct Approach to the Problem of Diffraction by a Half-Plane under Mixed Boundary Conditions

A general direct technique of solving a mixed boundary value problem in the theory of diffraction by a semi-infinite plane is presented. Taking account of the correct edge-conditions, the unique solution of the problem is derived, by means of Jones' method in the theory of Wiener-Hopf technique, in the case of incident plane wave. The solution of the half-plane problem is found out in exact form. (The far-field is derived by the method of steepest descent.) It is observed that it is not the Wiener-Hopf technique which really needs any modification but a new technique is certainly required to handle the peculiar type of coupled integral equations which the Wiener-Hopf technique leads to. Eine allgemeine direkte Technik zur Lösung eines gemischten Randwertproblems in der Theorie der Beugung an einer halbunendlichen Ebene wird vorgestellt. Unter Berücksichtigung der korrekten Eckbedingungen wird mit der Methode von Jones aus der Theorie der Wiener-Hopf-Technik die eindeutige Lösung für den Fall der einfallenden ebenen Welle hergeleitet. Die Lösung des Halbebenenproblems wird in exakter Form angegeben. (Das Fernfeld wurde mit der Methode des steilsten Abstiegs bestimmt.) Es wurde bemerkt, daß es nicht die Wiener-Hopf-Technik ist, die wirklich irgend welcher Modifikationen bedurfte. Gewiß aber wird eine neue Technik zur Behandlung des besonderen Typs gekoppelter Integralgleichungen benötigt, auf die die Wiener-Hopf-Technik führt.

A New Approach to the Problem of Scattering of Water Waves by Vertical Barriers

Using a modified Green's function technique the two well-known basic problems of scattering of surface water waves by vertical barriers are reduced to the problem of solving a pair of uncoupled integral equations involving the “jump” and “sum” of the limiting values of the velocity potential on the two sides of the barriers in each case. These integral equations are then solved, in closed form, by the aid of an integral transform technique involving a general trigonometric kernel as applicable to the problems associated with a radiation condition.

Exact traveling- wave solution for model geophysical systems

Exact traveling-wave solutions of time-dependent nonlinear inhomogeneous PDEs, describing several model systems in geophysical fluid dynamics, are found. The reduced nonlinear ODEs are treated as systems of linear algebraic equations in the derivatives. A variety of solutions are found, depending on the rank of the algebraic systems. The geophysical systems include acoustic gravity waves, inertial waves, and Rossby waves. The solutions describe waves which are, in general, either periodic or monoclinic. The present approach is compared with the earlier one due to Grundland (1974) for finding exact solutions of inhomogeneous systems of nonlinear PDEs.

Cooling of an infinite slab in a two-fluid medium

A mixed boundary-valued problem associated with the diffusion equation, that involves the physical problem of cooling of an infinite slab in a two-fluid medium, is solved completely by using the Wiener-Hopf technique. An analytical solution is derived for the temperature distribution at the quench fronts being created by two different layers of cold fluids having different cooling abilities moving on the upper surface of the slab at constant speed. Simple expressions are derived for the values of the sputtering temperatures of the slab at the points of contact with the respective layers, assuming one layer of the fluid to be of finite extent and the other of infinite extent. The main problem is solved through a three-part Wiener - Hopf problem of a special type, and the numerical results under certain special circumstances are obtained and presented in the form of a table.

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey

This work is a survey of the average cost control problem for discrete-time Markov processes. The authors have attempted to put together a comprehensive account of the considerable research on this problem over the past three decades. The exposition ranges from finite to Borel state and action spaces and includes a variety of methodologies to find and characterize optimal policies. The authors have included a brief historical perspective of the research efforts in this area and have compiled a substantial yet not exhaustive bibliography. The authors have also identified several important questions that are still open to investigation.

On extremal solutions to stochastic control problems, II

The set of attainable laws of the joint state-control process of a controlled diffusion is analyzed from a convex analytic viewpoint. Various equivalence relations depending on one-dimensional marginals thereof are defined on this set and the corresponding equivalence classes are studied.

Transient Flow of a Compressible Viscous Fluid Near an Infinite Disk

We have consider ed the transient motion of art electrically conducting viscous compressible fluid which is in contact with an insulated infinite disk. The initial motion is considered to be due to the uniform rotation of the disk in an otherwise stationary fluid or due to the uniform rigid rotation of the fluid over a stationary disk. Different cases of transient motion due to finite impulse imparted either to the disk or to the distant fluid have been investigated. Effects of the imposed axial magnetic field and the disk temperature on the transient flow are included. The nonlinear partial differential equations governing the motion are solved numerically using an implicit finite-difference scheme along with the Newton's linearisation technique.

Exact-Solutions Of Linear Partial-Differential Equations With Variable-Coefficients

Backlund transformations relating the solutions of linear PDE with variable coefficients to those of PDE with constant coefficients are found, generalizing the study of Varley and Seymour [2]. Auto-Backlund transformations are also determined. To facilitate the generation of new solutions via Backlund transformation, explicit solutions of both classes of the PDE just mentioned are found using invariance properties of these equations and other methods. Some of these solutions are new.

A formula for the solution of general Abel integral equation

A new formula for the solution of the general Abel Integral equation is derived, and an important special case is checked with the known result.

Concise row-pruning algorithm to invert a matrix

Presented here, in a vector formulation, is an O(mn2) direct concise algorithm that prunes/identifies the linearly dependent (ld) rows of an arbitrary m X n matrix A and computes its reflexive type minimum norm inverse A(mr)-, which will be the true inverse A-1 if A is nonsingular and the Moore-Penrose inverse A+ if A is full row-rank. The algorithm, without any additional computation, produces the projection operator P = (I - A(mr)- A) that provides a means to compute any of the solutions of the consistent linear equation Ax = b since the general solution may be expressed as x = A(mr)+b + Pz, where z is an arbitrary vector. The rank r of A will also be produced in the process. Some of the salient features of this algorithm are that (i) the algorithm is concise, (ii) the minimum norm least squares solution for consistent/inconsistent equations is readily computable when A is full row-rank (else, a minimum norm solution for consistent equations is obtainable), (iii) the algorithm identifies ld rows, if any, and reduces concerned computation and improves accuracy of the result, (iv) error-bounds for the inverse as well as the solution x for Ax = b are readily computable, (v) error-free computation of the inverse, solution vector, rank, and projection operator and its inherent parallel implementation are straightforward, (vi) it is suitable for vector (pipeline) machines, and (vii) the inverse produced by the algorithm can be used to solve under-/overdetermined linear systems.

Exact free-surface flows for shallow-water equations .1. - the incompressible case

A comprehensive exact treatment of free surface flows governed by shallow water equations (in sigma variables) is given. Several new families of exact solutions of the governing PDEs are found and are shown to embed the well-known self-similar or traveling wave solutions which themselves are governed by reduced ODEs. The classes of solutions found here are explicit in contrast to those found earlier in an implicit form. The height of the free surface for each family of solutions is found explicitly. For the traveling or simple wave, the free surface is governed by a nonlinear wave equation, but is arbitrary otherwise. For other types of solutions, the height of the free surface is constant either on lines of constant acceleration or on lines of constant speed; in another case, the free surface is a horizontal plane while the flow underneath is a sine wave. The existence of simple waves on shear flows is analytically proved. The interaction of large amplitude progressive waves with shear flow is also studied.