DETERMINISTIC ALGORITHMS FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

Probabilistic seismic hazard analysis for Bangalore

This article presents the results of probabilistic seismic hazard analysis (PSHA) for Bangalore, South India. Analyses have been carried out considering the seismotectonic parameters of the region covering a radius of 350 km keeping Bangalore as the center. Seismic hazard parameter `b' has been evaluated considering the available earthquake data using (1) Gutenberg-Richter (G-R) relationship and (2) Kijko and Sellevoll (1989, 1992) method utilizing extreme and complete catalogs. The `b' parameter was estimated to be 0.62 to 0.98 from G-R relation and 0.87 +/- A 0.03 from Kijko and Sellevoll method. The results obtained are a little higher than the `b' values published earlier for southern India. Further, probabilistic seismic hazard analysis for Bangalore region has been carried out considering six seismogenic sources. From the analysis, mean annual rate of exceedance and cumulative probability hazard curve for peak ground acceleration (PGA) and spectral acceleration (Sa) have been generated. The quantified hazard values in terms of the rock level peak ground acceleration (PGA) are mapped for 10% probability of exceedance in 50 years on a grid size of 0.5 km x 0.5 km. In addition, Uniform Hazard Response Spectrum (UHRS) at rock level is also developed for the 5% damping corresponding to 10% probability of exceedance in 50 years. The peak ground acceleration (PGA) value of 0.121 g obtained from the present investigation is slightly lower (but comparable) than the PGA values obtained from the deterministic seismic hazard analysis (DSHA) for the same area. However, the PGA value obtained in the current investigation is higher than PGA values reported in the global seismic hazard assessment program (GSHAP) maps of Bhatia et al. (1999) for the shield area.

Reservoir Operation for Hydropower Optimization: A Chance-Constrained Approach

This paper presents a chance-constrained linear programming formulation for reservoir operation of a multipurpose reservoir. The release policy is defined by a chance constraint that the probability of irrigation release in any period equalling or exceeding the irrigation demand is at least equal to a specified value P (called reliability level). The model determines the maximum annual hydropower produced while meeting the irrigation demand at a specified reliability level. The model considers variation in reservoir water level elevation and also the operating range within which the turbine operates. A linear approximation for nonlinear power production function is assumed and the solution obtained within a specified tolerance limit. The inflow into the reservoir is considered random. The chance constraint is converted into its deterministic equivalent using a linear decision rule and inflow probability distribution. The model application is demonstrated through a case study.

Species-area and species-individual relationships for tropical trees: A comparison of three 50-ha plots

1 Species-accumulation curves for woody plants were calculated in three tropical forests, based on fully mapped 50-ha plots in wet, old-growth forest in Peninsular Malaysia, in moist, old-growth forest in central Panama, and in dry, previously logged forest in southern India. A total of 610 000 stems were identified to species and mapped to < Im accuracy. Mean species number and stem number were calculated in quadrats as small as 5 m x 5 m to as large as 1000 m x 500 m, for a variety of stem sizes above 10 mm in diameter. Species-area curves were generated by plotting species number as a function of quadrat size; species-individual curves were generated from the same data, but using stem number as the independent variable rather than area. 2 Species-area curves had different forms for stems of different diameters, but species-individual curves were nearly independent of diameter class. With < 10(4) stems, species-individual curves were concave downward on log-log plots, with curves from different forests diverging, but beyond about 104 stems, the log-log curves became nearly linear, with all three sites having a similar slope. This indicates an asymptotic difference in richness between forests: the Malaysian site had 2.7 times as many species as Panama, which in turn was 3.3 times as rich as India. 3 Other details of the species-accumulation relationship were remarkably similar between the three sites. Rectangular quadrats had 5-27% more species than square quadrats of the same area, with longer and narrower quadrats increasingly diverse. Random samples of stems drawn from the entire 50 ha had 10-30% more species than square quadrats with the same number of stems. At both Pasoh and BCI, but not Mudumalai. species richness was slightly higher among intermediate-sized stems (50-100mm in diameter) than in either smaller or larger sizes, These patterns reflect aggregated distributions of individual species, plus weak density-dependent forces that tend to smooth the species abundance distribution and 'loosen' aggregations as stems grow. 4 The results provide support for the view that within each tree community, many species have their abundance and distribution guided more by random drift than deterministic interactions. The drift model predicts that the species-accumulation curve will have a declining slope on a log-log plot, reaching a slope of O.1 in about 50 ha. No other model of community structure can make such a precise prediction. 5 The results demonstrate that diversity studies based on different stem diameters can be compared by sampling identical numbers of stems. Moreover, they indicate that stem counts < 1000 in tropical forests will underestimate the percentage difference in species richness between two diverse sites. Fortunately, standard diversity indices (Fisher's sc, Shannon-Wiener) captured diversity differences in small stem samples more effectively than raw species richness, but both were sample size dependent. Two nonparametric richness estimators (Chao. jackknife) performed poorly, greatly underestimating true species richness.

Response And Stability Of A Stochastic Beam-Column Using Stochastic Fem

A beam-column resting on continuous Winkler foundation and discrete elastic supports is considered. The beam-column is of variable cross-section and the variation of sectional properties along the axis of the beam-column is deterministic. Young's modulus, mass per unit length and distributed axial loadings of the beam-column have a stochastic distribution. The foundation stiffness coefficient of the Winkler model, the stiffnesses of discrete elastic supports, stiffnesses of end springs and the end thrust, are all considered as random parameters. The material property fluctuations and distributed axial loadings are considered to constitute independent, one-dimension uni-variate homogeneous real stochastic fields in space. The foundation stiffness coefficient, stiffnesses of the discrete elastic supports, stiffnesses of end springs and the end thrust are considered to constitute independent random variables. Static response, free vibration and stability behaviour of the beam-column are studied. Hamilton's principle is used to formulate the problem using stochastic FEM. Sensitivity vectors of the response and stability parameters are evaluated. Using these statistics of free vibration frequencies, mode shapes, buckling parameters, etc., are evaluated. A numerical example is given.

A pseudo-dynamical systems approach to a class of inverse problems in engineering

A pseudo-dynamical approach for a class of inverse problems involving static measurements is proposed and explored. Following linearization of the minimizing functional associated with the underlying optimization problem, the new strategy results in a system of linearized ordinary differential equations (ODEs) whose steady-state solutions yield the desired reconstruction. We consider some explicit and implicit schemes for integrating the ODEs and thus establish a deterministic reconstruction strategy without an explicit use of regularization. A stochastic reconstruction strategy is then developed making use of an ensemble Kalman filter wherein these ODEs serve as the measurement model. Finally, we assess the numerical efficacy of the developed tools against a few linear and nonlinear inverse problems of engineering interest.

Byzantine-resilient distributed computing systems

This paper is aimed at reviewing the notion of Byzantine-resilient distributed computing systems, the relevant protocols and their possible applications as reported in the literature. The three agreement problems, namely, the consensus problem, the interactive consistency problem, and the generals problem have been discussed. Various agreement protocols for the Byzantine generals problem have been summarized in terms of their performance and level of fault-tolerance. The three classes of Byzantine agreement protocols discussed are the deterministic, randomized, and approximate agreement protocols. Finally, application of the Byzantine agreement protocols to clock synchronization is highlighted.

Optimal scheduling of hydro-thermal power systems under shortage

The problem of optimal scheduling of the generation of a hydro-thermal power system that is faced with a shortage of energy is studied. The deterministic version of the problem is first analyzed, and the results are then extended to cases where the loads and the hydro inflows are random variables.

Timing the Emergence of Resistance to Anti-HIV Drugs with Large Genetic Barriers

New antiretroviral drugs that offer large genetic barriers to resistance, such as the recently approved inhibitors of HIV-1 protease, tipranavir and darunavir, present promising weapons to avert the failure of current therapies for HIV infection. Optimal treatment strategies with the new drugs, however, are yet to be established. A key limitation is the poor understanding of the process by which HIV surmounts large genetic barriers to resistance. Extant models of HIV dynamics are predicated on the predominance of deterministic forces underlying the emergence of resistant genomes. In contrast, stochastic forces may dominate, especially when the genetic barrier is large, and delay the emergence of resistant genomes. We develop a mathematical model of HIV dynamics under the influence of an antiretroviral drug to predict the waiting time for the emergence of genomes that carry the requisite mutations to overcome the genetic barrier of the drug. We apply our model to describe the development of resistance to tipranavir in in vitro serial passage experiments. Model predictions of the times of emergence of different mutant genomes with increasing resistance to tipranavir are in quantitative agreement with experiments, indicating that our model captures the dynamics of the development of resistance to antiretroviral drugs accurately. Further, model predictions provide insights into the influence of underlying evolutionary processes such as recombination on the development of resistance, and suggest guidelines for drug design: drugs that offer large genetic barriers to resistance with resistance sites tightly localized on the viral genome and exhibiting positive epistatic interactions maximally inhibit the emergence of resistant genomes.

Approximate closed-form solutions of realistic true proportional navigation guidance using the Adomian decomposition method

Approximate closed-form solutions of the non-linear relative equations of motion of an interceptor pursuing a target under the realistic true proportional navigation (RTPN) guidance law are derived using the Adomian decomposition method in this article. In the literature, no study has been reported on derivation of explicit time-series solutions in closed form of the nonlinear dynamic engagement equations under the RTPN guidance. The Adomian method provides an analytical approximation, requiring no linearization or direct integration of the non-linear terms. The complete derivation of the Adomian polynomials for the analysis of the dynamics of engagement under RTPN guidance is presented for deterministic ideal case, and non-ideal dynamics in the loop that comprises autopilot and actuator dynamics and target manoeuvre, as well as, for a stochastic case. Numerical results illustrate the applicability of the method.

Analysis of randomly time varying systems by gaussian closure technique

The Gaussian probability closure technique is applied to study the random response of multidegree of freedom stochastically time varying systems under non-Gaussian excitations. Under the assumption that the response, the coefficient and the excitation processes are jointly Gaussian, deterministic equations are derived for the first two response moments. It is further shown that this technique leads to the best Gaussian estimate in a minimum mean square error sense. An example problem is solved which demonstrates the capability of this technique for handling non-linearity, stochastic system parameters and amplitude limited responses in a unified manner. Numerical results obtained through the Gaussian closure technique compare well with the exact solutions.

On the Conversion of Hensel Codes to Farey Rationals

Three different algorithms are described for the conversion of Hensel codes to Farey rationals. The first algorithm is based on the trial and error factorization of the weight of a Hensel code, inversion and range test. The second algorithm is deterministic and uses a pair of different p-adic systems for simultaneous computation; from the resulting weights of the two different Hensel codes of the same rational, two equivalence classes of rationals are generated using the respective primitive roots. The intersection of these two equivalence classes uniquely identifies the rational. Both the above algorithms are exponential (in time and/or space).

Nonstationary Random Critical Seismic Excitations

A method is presented to find nonstationary random seismic excitations with a constraint on mean square value such that the response variance of a given linear system is maximized. It is also possible to incorporate the dominant input frequency into the analysis. The excitation is taken to be the product of a deterministic enveloping function and a zero mean Gaussian stationary random process. The power spectral density function of this process is determined such that the response variance is maximized. Numerical results are presented for a single-degree system and an earth embankment modeled as shear beam.

Functional programming systems revisited

Functional Programming (FP) systems are modified and extended to form Nondeterministic Functional Programming (NFP) systems in which nondeterministic programs can be specified and both deterministic and nondeterministic programs can be verified essentially within the system. It is shown that the algebra of NFP programs has simpler laws in comparison with the algebra of FP programs. "Regular" forms are introduced to put forward a disciplined way of reasoning about programs. Finally, an alternative definition of "linear" forms is proposed for reasoning about recursively defined programs. This definition, when used to test the linearity of forms, results in simpler verification conditions than those generated by the original definition of linear forms.

Stochastic modelling of monthly rainfall

A transformation is suggested which can transform a non-Gaussian monthly hydrological time series into a Gaussian one. The suggested approach is verified with data of ten Indian rainfall time series. Incidentally, it is observed that once the deterministic trends are removed, the transformation leads to an uncorrelated process for monthly rainfall. The procedure for normalization is general enough in that it should be also applicable to river discharges. This is verified to a limited extent by considering data of two Indian river discharges.