Near optimal control of queueing networks over a finite time horizon

We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuous linear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line. Research supported in part by Israel Science Foundation Grant 249/02 and 454/05 and by European Network of Excellence Euro-NGI.     

Singular Double Porosity Model

We consider the linear parabolic equation describing the transport of a contaminant in a porous media crossed by a net of infinitely thin fractures. The permeability is very high in the fractures but very low in the porous blocks. We derive the homogenized model corresponding to a net of infinitely thin fractures, by means of the singular measures technique. We assume that these singular measures are supported by hyperplanes of codimension one. We prove in a second step that this homogenized model could be obtained indistinctly either by letting the fracture thickness, in the standard double porosity model, tend to zero, or by homogenizing a model with infinitely thin fractures.     

Some theoretical results on the Grouped Variables Lasso

We consider the linear regression model with Gaussian error. We estimate the unknown parameters by a procedure inspired by the Group Lasso estimator introduced in [22]. We show that this estimator satisfies a sparsity inequality, i.e., a bound in terms of the number of non-zero components of the oracle regression vector. We prove that this bound is better, in some cases, than the one achieved by the Lasso and the Dantzig selector.      

How Many Comparisons Does Quicksort Use?

We examine the probability distribution of the number of comparisons needed by the Quicksort sorting algorithm, where probability arises due to the items being in random order. We develop a general class of distributions for the permutation of the items to be sorted which includes the uniform distribution on permutations as a special case. For this general class, the distribution of the number of comparisons is given by the solution of a simple recurrence relation. We provide an exact solution of the recurrence for very small n. We show that the solution can be approximated asymptotically by the solution of a "quadratic" operator equation. We exhibit three numerical solutions to the operator equation for two different distributions on permutations from the general class. We also exhibit numerical solutions for the case in which the algorithm is modified so that arrays are partitioned by the median-of-three selected items rather than by a single selected item.     

Convergence of subsets of a complete geodesic space with curvature bounded above

We consider a notion of set-convergence in a Hadamard space recently defined by Kimura and extend it to that in a complete geodesic space with curvature bounded above by a positive number. We obtain its equivalent condition by using the corresponding sequence of metric projections. We also discuss the Kadec–Klee property on such spaces and interaction among this set-convergence having different curvatures.     

Realizability of words in mosaic labyrinths

In this paper we study mosaic labyrinths with the help of words generated by them in the alphabet of labels attached to arcs and vertices of a labyrinth. We consider the problem of the characterization of words generated by a labyrinth. We propose a constructive recognition criterion, it defines whether a word is generated by a labyrinth or not. We establish conditions under which a word can be generated by a unique labyrinth, by a finite number of labyrinths, or by infinitely many labyrinths.     

On computing in fine-grained compartmentalised Belousov–Zhabotinsky medium

We introduce results of computer experiments on information processing in a hexagonal array of vesicles filled with Belousov–Zhabotinsky (BZ) solution in a sub-excitable mode. We represent values of Boolean variables by excitation wave-fragments and implement basic logical gates by colliding the wave-fragments. We show that a vesicle filled with BZ mixture can implement a range of basic logical functions. We cascade BZ-vesicle logical gates into arithmetic circuits implementing addition of two one-bit binary numbers. We envisage that our theoretical results will be applied in chemical laboratory designs of massive-parallel computers based on fine-grained compartmentalisation of excitable chemical systems.     

Valid inequalities based on the interpolation procedure

We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in Dash and Gunluk (2003). We first analyze and extend the shooting experiment described in Gomory, Johnson and Evans. We show that MIR based inequalities dominate inequalities generated by the interpolation procedure in some important cases. We also show that the Gomory mixed-integer cut is likely to dominate any inequality generated by the interpolation procedure in a certain probabilistic sense. We also generalize a result of Cornuéjols, Li and Vandenbussche (2003) on comparing the strength of the Gomory mixed-integer cut with related inequalities.     

Lotka-Volterra equations in three dimensions satisfying the Kowalevski-Painlevé property

We examine a class of Lotka-Volterra equations in three dimensions which satisfy the Kowalevski-Painlevé property. We restrict our attention to Lotka-Volterra systems defined by a skew symmetric matrix. We obtain a complete classification of such systems. The classification is obtained using Painlevé analysis and more specifically by the use of Kowalevski exponents. The imposition of certain integrality conditions on the Kowalevski exponents gives necessary conditions. We also show that the conditions are sufficient.     

Schrödinger Operator Perturbed by Operators Related to Null Sets

We discuss the Schrödinger operator with positive singular perturbations given by operators which act in the space constructed by a positive measure supported by a null set. We construct examples when perturbations are given by the one-dimensional Laplacian on a segment.     

Homotopy analysis method with a non-homogeneous term in the auxiliary linear operator

We demonstrate the efficiency of a modification of the normal homotopy analysis method (HAM) proposed by Liao [2] by including a non-homogeneous term in the auxiliary linear operator (this can be considered as a special case of “further generalization” of HAM given by Liao in [2]). We then apply the modified method to a few examples. It is observed that including a non-homogeneous term gives faster convergence in comparison to normal HAM. We also prove a convergence theorem, which shows that our technique yields the convergent solution.     

A nonlinear programming approach for the sliding mode control design

We treat the sliding mode control problem by formulating it as a two phase problem consisting of reaching and sliding phases. We show that such a problem can be formulated as bicriteria nonlinear programming problem by associating each of these phases with an appropriate objective function and constraints. We then scalarize this problem by taking weighted sum of these objective functions. We show that by solving a sequence of such formulated nonlinear programming problems it is possible to obtain sliding mode controller feedback coefficients which yield a competitive performance throughout the control. We solve the nonlinear programming problems so constructed by using the modified subgradient method which does not require any convexity and differentiability assumptions. We illustrate validity of our approach by generating a sliding mode control input function for stabilization of an inverted pendulum.     

A free boundary problem for the Laplacian with a constant Bernoulli-type boundary condition

We study a free boundary problem for the Laplace operator, where we impose a Bernoulli-type boundary condition. We show that there exists a solution to this problem. We use A. Beurling’s technique, by defining two classes of sub- and super-solutions and a Perron argument. We try to generalize here a previous work of A. Henrot and H. Shahgholian. We extend these results in different directions.     

Generation of simulation input scenarios using bootstrap methods

Simulation modellers frequently face a choice between fidelity and variety in their input scenarios. Using an historical trace provides only one realistic scenario. Using the input modelling facilities in commercial simulation software may provide any number of unrealistic scenarios. We ease this dilemma by developing a way to use the moving blocks bootstrap to convert a single trace into an unlimited number of realistic input scenarios. We do this by setting the bootstrap block size to make the bootstrap samples mimic independent realizations in terms of the distribution of distance between pairs of inputs. We measure distance using a new statistic computed from zero crossings. We estimate the best block size by scaling up an estimate computed by analysing subseries of the trace.     

An approximate Herbrand’s theorem and definable functions in metric structures

We develop a version of Herbrand's theorem for continuous logic and use it to prove that definable functions in infinite‐dimensional Hilbert spaces are piecewise approximable by affine functions. We obtain similar results for definable functions in Hilbert spaces expanded by a group of generic unitary operators and Hilbert spaces expanded by a generic subspace. We also show how Herbrand's theorem can be used to characterize definable functions in absolutely ubiquitous structures from classical logic.     

A Product Partition Model With Regression on Covariates

We propose a probability model for random partitions in the presence of covariates. In other words, we develop a model-based clustering algorithm that exploits available covariates. The motivating application is predicting time to progression for patients in a breast cancer trial. We proceed by reporting a weighted average of the responses of clusters of earlier patients. The weights should be determined by the similarity of the new patient’s covariate with the covariates of patients in each cluster. We achieve the desired inference by defining a random partition model that includes a regression on covariates. Patients with similar covariates are a priori more likely to be clustered together. Posterior predictive inference in this model formalizes the desired prediction.

We build on product partition models (PPM). We define an extension of the PPM to include a regression on covariates by including in the cohesion function a new factor that increases the probability of experimental units with similar covariates to be included in the same cluster. We discuss implementations suitable for any combination of continuous, categorical, count, and ordinal covariates.

An implementation of the proposed model as R-package is available for download.     

Graphs of maps between manifolds in trace spaces and with vanishing mean oscillation

We give a positive answer to a question raised by Alberti in connection with a recent result by Brezis and Nguyen. We show the existence of currents associated with graphs of maps in trace spaces that have vanishing mean oscillation. The degree of such maps may be written in terms of these currents, of which we give some structure properties. We also deal with relevant examples.     

Optimally accurate Petrov-Galerkin method of finite elements

We perform analysis for a finite elements method applied to the singular self-adjoint problem. This method uses continuous piecewise polynomial spaces for the trial and the test spaces. We fit the trial polynomial space by piecewise exponentials and we apply so exponentially fitted Galerkin method to singular self-adjoint problem by approximating driving terms by Lagrange piecewise polynomials, linear, quadratic and cubic. We measure the erroe in max norm. We show that method is optimal of the first order in the error estimate. We also give numerical results for the Galerkin approximation.     

INITIAL VALUE TECHNIQUES FOR THE HELMHOLTZ AND MAXWELL EQUATIONS

We study the initial value problem of the Helmholtz equation with spatially variable wave number. We show that it can be stabilized by suppressing the evanescent waves. The stabilized Helmholtz equation can be solved numerically by a marching scheme combined with FFT. The resulting algorithm has complexity n^2 log n on a n x n grid. We demonstrate the efficacy of the method by numerical examples with caustics. For the Maxwell equation the same treatment is possible after reducing it to a second order system. We show how the method can be used for inverse problems arising in acoustic tomography and microwave imaging.