Stochastic Enumeration Method for Counting NP-Hard Problems

We present a new generic sequential importance sampling algorithm, called stochastic enumeration (SE) for counting #P-complete problems, such as the number of satisfiability assignments and the number of perfect matchings (permanent). We show that SE presents a natural generalization of the classic one-step-look-ahead algorithm in the sense that it: Runs in parallel multiple trajectories instead of a single one; Employs a polynomial time decision making oracle, which can be viewed as an n-step-look-ahead algorithm, where n is the size of the problem. Our simulation studies indicate good performance of SE as compared with the well-known splitting and SampleSearch methods.     

Generalized Grunsky coefficients and inequalities

The generalized Grunsky coefficients are defined in this paper for all locally univalent meromorphic functions in any domain in the complete complex plane. Various explicit formulas for these coefficients are established. Necessary conditions for univalence are obtained in arbitrary domains and in the unit disc in particular. The first one generalizes Grunsky inequalities and the second one is an extension of the Nehari-Schwarzian derivative condition.     

Error analysis for regenerative queueing estimators with special reference to gradient estimators via likelihood ratio

The performance of telecommunications systems is typically estimated (either analytically or by simulation) via queueing theoretic models. The gradient of the expected performance with respect to the various parameters (such as arrival rate or service rate) is very important as it not only measures the sensitivity to change, but is also needed for the solution of optimization problems. While the estimator for the expected performance is the sample mean of the simulation experiment, there are several possibilities for the estimator of the gradient. They include the obvious finite difference approximation, but also other recently advocated techniques, such as estimators derived from likelihood ratio transformations or from infinitesimal perturbations. A major problem in deciding upon which estimator to use and in planning the length of the simulation has been the scarcity of analytical error calculations for estimators of queueing models. It is this question that we answer in this paper for the waiting time moments (of arbitrary order) of theM / G / 1 queue by using the queueing analysis technique developed by Shalmon. We present formulas for the error variance of the estimators of expectation and of its gradient as a function of the simulation length; at arbitrary traffic intensity the formulas are recursive, while the heavy traffic approximations are explicit and of very simple form. For the gradient of the mean waiting time with respect to the arrival (or service) rate, and at 1 percent relative precision, the heavy traffic formulas show that the likelihood ratio estimator for the gradient reduces the length of the simulation required by the finite difference estimator by about one order of magnitude; further increasing the relative precision by a factor increases the reduction advantage by the same factor. At any relative precision, it exceeds the length of the simulation required for the estimation of the mean with the same relative precision by about one order of magnitude. While strictly true for theM / G / 1 queue, the formulas can also be used as guidelines in the planning of queueing simulations and of stochastic optimizations of complex queueing systems, particularly those with Poisson arivals.     

Hyperbolic metric,curvature of geodesics and hyperbolic discs in hyperbolic plane domains

The purpose of this paper is to investigate the relations among some geometric quantities defined for every hyperbolic plane domain of any connectivity, each of which measures, in some sense, how much the domain deviates either from a disc, convex domain, or simply connected domain on one hand, or a punctured domain on the other hand. Supported by the Landau Center for Mathematical Research in Analysis.     

Decomposable score function estimators for sensitivity analysis and optimization of queueing networks

This paper surveys some recent results and presents some new results on the so-called decomposable and truncated score functions (DSF and TSF) estimators for performance evaluation, sensitivity analysis and optimization of open non-Markovian (non-product) queueing networks. The idea behind the TSF estimators is based on truncation of the score function process, while the idea behind the DSF estimators is to decompose the queueing network into smaller units, calledmodules, such that each module contains several connected queues, and then approximate the unknown quantities by treating these modules as if they were completely independent. In other words, in the DSF estimators we use frequently occurrentlocal regenerative cycles at eachindividual module instead oftrue but seldom occurrentglobal ones of theentire system. Although the local cycles at each module interact with their neighbors, our numerical studies show that typically the contribution from the neighbors is quite small and thus DSF estimators approximate the unknown quantities rather well, in the sense that their bias is reasonably small and the variance is much smaller than that of the standard score function estimators. Both DSF and TSF estimators were implemented in a simulation package, called thequeueing network stabilizer and optimizer (QNSO). This package is suitable for performance evaluation, sensitivity analysis and optimization of general open non-Markovian queueing networks with respect to the parameter vector of an exponential family of distributions.Research supported by the L. Edelstein Research Fund of the Technion — Israel Institute of Technology and École Polytechnique Fédérale de Lausanne, Switzerland.     

Molecular-orbital realizations of the bent-bond model: Spiranic derivatives of cyclobutanone

In the frame of our studies on small-ring compounds, we deal here with structures in which a three-membered ring and a carbonylated four-membered ring are fixed in close proximity. The theoretical approach is through an allvalence electron semiempirical method. The experimental background, based on results of other workers, comprises mainly UV and IR spectral data. The main topics to be discussed are: charge-donation and charge-transfer from the 3-ring, hypsochromic and bathochromic shifts of electronic transitions related to the carbonyl, direct substituent effects on the carbonyl stretching frequency, and the across-ring interaction in cyclobutanone.Part XII in series. For previous papers, see Refs. [1, 2].     

Light-dependent Oxygen Consumption in Bacteriochlorophyll-Serine-treated Melanoma Tumors: On-line Determination Using a Tissue-inserted Oxygen Microsensor

Successful application of anticancer therapy, and especially photodynamic therapy (PDT) mediated by type II (PDTII) processes, depends on the oxygen content within the tumor before, during and after treatment. The high consumption of oxygen during type II PDT imposes constraints on therapy strategies. Although rates of oxygen consumption and repletion during PDTII were suggested by theoretical studies, direct measurements have not been reported. Application of a novel oxygen sensor allowed continuous and direct in situ measurements (up to a depth of 8–9 mm from the tumor surface and for several hours) of temporal variations in the oxygen partial pressure (pO₂) during PDT. Highly pigmented M2R mouse melanoma tumors implanted in CD1 nude mice were treated with bacteriochlorophyll-serine (Bchl-Ser; a new photodynamic reagent) and were subjected to fractionated illumination (700 < λ. < 900 nm) at a fluence rate of 12 mW cm^-2. This illumination led to total oxygen depletion with an average consumption rate of 7.2 uAf(O₂) s^-1. Spontaneous reoxygenation (at an average rate of 2.5 µM(O₂)/s) was observed during the following dark period. These rates are in good agreement with theoretical considerations (Foster et al., Radiat. Res. 126, 296,1991 and Henning et al, Radiat. Res. 142, 221, 1995). The observed patterns of oxygen consumption and recovery during prolonged periods of light/dark cycles were interpreted in terms of vasculature damage and sensitizer clearance. The presented data support the previously suggested advantages of fractionated illumination for type II photodynamic processes.     

Flow-dependent optofluidic particle trapping and circulation

Microfluidics and fiber optics are integrated in-plane to achieve several flow-dependent particle trapping mechanisms on-chip. Each mechanism results from a combination of fluid drag and optical scattering forces. Parallel and offset fibers, orthogonally oriented to the flow, show cyclic cross-stream particle transit with flow-dependent particle trajectories and loss. Upstream-angled fibers with flow result in circulatory particle trajectories. Asymmetric angled fibers result in continuous particle circulation whereas symmetry with respect to the flow axis enables both stable trapping and circulation modes. Stable trapping of single particles, self-guided multi-particle arrays and particle assemblies are demonstrated with a single upstream-oriented fiber. Size tuning of trapped multiple particle assemblies is also presented. The planar interaction of fluid drag and optical forces results in novel possibilities for cost-effective on-chip diagnostics, mixing, flow rate monitoring, and cell analysis.     

An analysis of the Brown–Biefeld effect

When a high voltage is applied on an asymmetric capacitor, it experiences a force acting toward its thinner electrode. This effect is called Brown–Biefeld effect (BB), after its discoverers Thomas Townsend Brown and Paul Alfred Biefeld. Many theories have been proposed to explain this effect, and many speculations can be found on the net suggesting the effect is an antigravitation or a space warp effect. However, in the recent years, more and more researchers attribute the BB effect to a unicharge ion wind. This work calculates the levitation force due to ion wind and presents experimental results which confirm the theoretical results.