Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Multigroup-Decodable STBCs from Clifford Algebras

A Space-Time Block Code (STBC) in K symbols (variables) is called g-group decodable STBC if its maximum-likelihood decoding metric can be written as a sum of g terms such that each term is a function of a subset of the K variables and each variable appears in only one term. In this paper we provide a general structure of the weight matrices of multi-group decodable codes using Clifford algebras. Without assuming that the number of variables in each group to be the same, a method of explicitly constructing the weight matrices of full-diversity, delay-optimal g-group decodable codes is presented for arbitrary number of antennas. For the special case of Nt=2a we construct two subclass of codes: (i) A class of 2a-group decodable codes with rate a2(a−1), which is, equivalently, a class of Single-Symbol Decodable codes, (ii) A class of (2a−2)-group decodable with rate (a−1)2(a−2), i.e., a class of Double-Symbol Decodable codes. Simulation results show that the DSD codes of this paper perform better than previously known Quasi-Orthogonal Designs.

Relay Precoder Optimization in MIMO-Relay Networks With Imperfect CSI

In this paper, we consider robust joint designs of relay precoder and destination receive filters in a nonregenerative multiple-input multiple-output (MIMO) relay network. The network consists of multiple source-destination node pairs assisted by a MIMO-relay node. The channel state information (CSI) available at the relay node is assumed to be imperfect. We consider robust designs for two models of CSI error. The first model is a stochastic error (SE) model, where the probability distribution of the CSI error is Gaussian. This model is applicable when the imperfect CSI is mainly due to errors in channel estimation. For this model, we propose robust minimum sum mean square error (SMSE), MSE-balancing, and relay transmit power minimizing precoder designs. The next model for the CSI error is a norm-bounded error (NBE) model, where the CSI error can be specified by an uncertainty set. This model is applicable when the CSI error is dominated by quantization errors. In this case, we adopt a worst-case design approach. For this model, we propose a robust precoder design that minimizes total relay transmit power under constraints on MSEs at the destination nodes. We show that the proposed robust design problems can be reformulated as convex optimization problems that can be solved efficiently using interior-point methods. We demonstrate the robust performance of the proposed design through simulations.

Convergence problems in a class of model reference adaptive control systems

A class of model reference adaptive control system which make use of an augmented error signal has been introduced by Monopoli. Convergence problems in this attractive class of systems have been investigated in this paper using concepts from hyperstability theory. It is shown that the condition on the linear part of the system has to be stronger than the one given earlier. A boundedness condition on the input to the linear part of the system has been taken into account in the analysis - this condition appears to have been missed in the previous applications of hyperstability theory. Sufficient conditions for the convergence of the adaptive gain to the desired value are also given.

Scattering theory and linear optimal control: Regulator and servo problems

In this paper, several known computational solutions are readily obtained in a very natural way for the linear regulator, fixed end-point and servo-mechanism problems using a certain frame-work from scattering theory. The relationships between the solutions to the linear regulator problem with different terminal costs and the interplay between the forward and backward equations have enabled a concise derivation of the partitioned equations, the forward-backward equations, and Chandrasekhar equations for the problem. These methods have been extended to the fixed end-point, servo, and tracking problems.

Homogenization of eigenvalue problems in perforated domains

In this paper, we treat some eigenvalue problems in periodically perforated domains and study the asymptotic behaviour of the eigenvalues and the eigenvectors when the number of holes in the domain increases to infinity Using the method of asymptotic expansion, we give explicit formula for the homogenized coefficients and expansion for eigenvalues and eigenvectors. If we denote by ε the size of each hole in the domain, then we obtain the following aysmptotic expansion for the eigenvalues: Dirichlet: λε = ε−2 λ + λ0 +O (ε), Stekloff: λε = ελ1 +O (ε2), Neumann: λε = λ0 + ελ1 +O (ε2).Using the method of energy, we prove a theorem of convergence in each case considered here. We briefly study correctors in the case of Neumann eigenvalue problem.

Mechanism design problems in carbon economics

Reduction of carbon emissions is of paramount importance in the context of global warming and climate change. Countries and global companies are now engaged in understanding systematic ways of solving carbon economics problems, aimed ultimately at achieving well defined emission targets. This paper proposes mechanism design as an approach to solving carbon economics problems. The paper first introduces carbon economics issues in the world today and next focuses on carbon economics problems facing global industries. The paper identifies four problems faced by global industries: carbon credit allocation (CCA), carbon credit buying (CCB), carbon credit selling (CCS), and carbon credit exchange (CCE). It is argued that these problems are best addressed as mechanism design problems. The discipline of mechanism design is founded on game theory and is concerned with settings where a social planner faces the problem of aggregating the announced preferences of multiple agents into a collective decision, when the actual preferences are not known publicly. The paper provides an overview of mechanism design and presents the challenges involved in designing mechanisms with desirable properties. To illustrate the application of mechanism design in carbon economics,the paper describes in detail one specific problem, the carbon credit allocation problem.

Two-dimensional approximations of 3-dimensional eigenvalue problems in plate-theory

The eigenvalues and eigenfunctions corresponding to the three-dimensional equations for the linear elastic equilibrium of a clamped plate of thickness 2ϵ, are shown to converge (in a specific sense) to the eigenvalues and eigenfunctions of the well-known two-dimensional biharmonic operator of plate theory, as ϵ approaches zero. In the process, it is found in particular that the displacements and stresses are indeed of the specific forms usually assumed a priori in the literature. It is also shown that the limit eigenvalues and eigenfunctions can be equivalently characterized as the leading terms in an asymptotic expansion of the three-dimensional solutions, in terms of powers of ϵ. The method presented here applies equally well to the stationary problem of linear plate theory, as shown elsewhere by P. Destuynder.

Smooth DMS-FEM: A new approach to solving nearly incompressible nonlinear elasto-static problems

The DMS-FEM, which enables functional approximations with C(1) or still higher inter-element continuity within an FEM-based meshing of the domain, has recently been proposed by Sunilkumar and Roy [39,40]. Through numerical explorations on linear elasto-static problems, the method was found to have conspicuously superior convergence characteristics as well as higher numerical stability against locking. These observations motivate the present study, which aims at extending and exploring the DMS-FEM to (geometrically) nonlinear elasto-static problems of interest in solid mechanics and assessing its numerical performance vis-a-vis the FEM. In particular, the DMS-FEM is shown to vastly outperform the FEM (presently implemented through the commercial software ANSYS (R)) as the former requires fewer linearization and load steps to achieve convergence. In addition, in the context of nearly incompressible nonlinear systems prone to volumetric locking and with no special numerical artefacts (e.g. stabilized or mixed weak forms) employed to arrest locking, the DMS-FEM is shown to approach the incompressibility limit much more closely and with significantly fewer iterations than the FEM. The numerical findings are suggestive of the important role that higher order (uniform) continuity of the approximated field variables play in overcoming volumetric locking and the great promise that the method holds for a range of other numerically ill-conditioned problems of interest in computational structural mechanics. (C) 2011 Elsevier Ltd. All rights reserved.

On porous wave maker problems

The problem of generation of surface water waves at tile interface of two immiscible liquids by a onesided porous wave maker is studied in both the cases of water of infinite as well as finite depth by suitable application of the generalisation of Havelock's expansion theorem. The solution of the the problem of reflection of water waves due to a fixed porous wall is derived as a particular case.

Solution of a class of surface water wave scattering problems involving non-reflecting vertical barriers

A large class of scattering problems of surface water waves by vertical barriers lead to mixed boundary value problems for Laplace equation. Specific attentions are paid, in the present article, to highlight an analytical method to handle this class of problems of surface water wave scattering, when the barriers in question are non-reflecting in nature. A new set of boundary conditions is proposed for such non-reflecting barriers and tile resulting boundary value problems are handled in the linearized theory of water waves. Three basic poblems of scattering by vertical barriers are solved. The present new theory of non-reflecting vertical barriers predict new transmission coefficients and tile solutions of tile mathematical problems turn out to be extremely simple and straight forward as compared to the solution for other types of barriers handled previously.