Performance of service policies in a specialized service system with parallel servers

This paper considers a scheduling problem occurring in a specialized service system with parallel servers. In the system, customers are divided into the “ordinary” and “special” categories according to their service needs. Ordinary customers can be served by any server, while special customers can be served only by the flexible servers. We assume that the service time for any ordinary customer is the same and all special customers have another common service time. We analyze three classes of service policies used in practice, namely, policies with priority, policies without priority and mixed policies. The worst-case performance ratios are obtained for all of these service policies.     

Insensitive versus efficient dynamic load balancing in networks without blocking

So-called Whittle networks have recently been shown to give tight approximations for the performance of non-locally balanced networks with blocking, including practical routing policies such as joining the shortest queue. In the present paper, we turn the attention to networks without blocking. To this end, we consider a set of “insensitive” dynamic load balancing schemes preserving the structure of Whittle networks in the case of infinite buffers and examine their efficiency. Using Hausdorff’s theorem, we prove that the optimal insensitive schemes are static in this case, i.e., routing decisions do not depend on the current state of the queues. On the other hand, simulations show that the performance of static policies is generally much worse than that of “non balanced” sensitive dynamic policies. This demonstrates that strict insensitivity and efficiency may be incompatible objectives for networks with dynamic load balancing in case of infinite buffers. AMS Subject Classifications 60K25 · 68M20     

Simulation based analysis of patient arrival to health care systems and evaluation of an operations improvement scheme

Various demands of different patients over both medical resource and time domains in health care systems raise requests of strategies for balanced system capacity from an operations perspective. In this paper, a quantitative modeling technique with both patient arrival and associated treatment process integrated are used to characterize health care system performance and evaluate system efficiency. The patient arrival process is described as a dynamic random Poisson process and patient treatments are characterized as consumption processes of various health care resources over time with a view of the “product line” used. The waiting time of patients and usage of health care resources are proposed as system performance measures based on their means, variances, and confidence intervals. A simulation considering patients with several various diseases is given to find a mechanism of conflicting factors in decisions of balanced system capacity, and an operation scheme of “evenly balanced load for bottlenecks” is obtained based on analysis of simulation outputs. Simul8 provides the software environment for the simulation.     

Conditional lexicographic orders in constraint satisfaction problems

The lexicographically-ordered CSP (“lexicographic CSP” or “LO-CSP” for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to a given variable is more important than any change in assignment to any less important variable. In this paper, we show how this representation can be extended to handle conditional preferences in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the importance ordering of variables. In this case, by obviating the “overwhelming advantage” effect with respect to the original variables and values, the representational capacity is significantly enhanced. For problems of the first type, any of the algorithms originally devised for ordinary LO-CSPs can also be used when some of the domain orderings are dependent on assignments to “parent” variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary LO-CSPs can be extended to handle CSPs with conditional domain orderings.     

Weyl-Eddington-Einstein affine gravity in the context of modern cosmology

We propose new models of the “affine” theory of gravity in multidimensional space-times with symmetric connections. We use and develop ideas of Weyl, Eddington, and Einstein, in particular, Einstein’s proposed method for obtaining the geometry using the Hamilton principle. More specifically, the connection coefficients are determined using a “geometric” Lagrangian that is an arbitrary function of the generalized (nonsymmetric) Ricci curvature tensor (and, possibly, other fundamental tensors) expressed in terms of the connection coefficients regarded as independent variables. Such a theory supplements the standard Einstein theory with dark energy (the cosmological constant, in the first approximation), a neutral massive (or tachyonic) meson, and massive (or tachyonic) scalar fields. These fields couple only to gravity and can generate dark matter and/or inflation. The new field masses (real or imaginary) have a geometric origin and must appear in any concrete model. The concrete choice of the Lagrangian determines further details of the theory, for example, the nature of the fields that can describe massive particles, tachyons, or even “phantoms.” In “natural” geometric theories, dark energy must also arise. The basic parameters of the theory (cosmological constant, mass, possible dimensionless constants) are theoretically indeterminate, but in the framework of modern “multiverse” ideas, this is more a virtue than a defect. We consider further extensions of the affine models and in more detail discuss approximate effective (“physical”) Lagrangians that can be applied to the cosmology of the early Universe.     

On the Number of Facets of Three-Dimensional Dirichlet Stereohedra III: Full Cubic Groups

We are interested in the maximum possible number of facets that Dirichlet stereohedra for three-dimensional crystallographic groups can have. In two previous papers, D. Bochiş and the second author studied the problem for noncubic groups. This paper deals with “full” cubic groups, while “quarter” cubic groups are left for a subsequent paper. Here, “full” and “quarter” refers to the recent classification of three-dimensional crystallographic groups by Conway, Delgado-Friedrichs, Huson and Thurston. This paper’s main result is that Dirichlet stereohedra for any of the 27 full groups cannot have more than 25 facets. We also find stereohedra with 17 facets for one of these groups. Research partially supported by the Spanish Ministry of Education and Science, grant number MTM2005-08618-C02-02.     

Conditional Viability for Impulse Differential Games

We introduce in this paper the concept of “impulse evolutionary game”. Examples of evolutionary games are usual differential games, differentiable games with history (path-dependent differential games), mutational differential games, etc. Impulse evolutionary systems and games cover in particular “hybrid systems” as well as “qualitative systems”. The conditional viability kernel of a constrained set (with a target) is the set of initial states such that for all strategies (regarded as continuous feedbacks) played by the second player, there exists a strategy of the first player such that the associated run starting from this initial state satisfies the constraints until it hits the target. This paper characterizes the concept of conditional viability kernel for “qualitative games” and of conditional valuation function for “qualitative games” maximinimizing an intertemporal criterion. The theorems obtained so far about viability/capturability issues for evolutionary systems, conditional viability for differential games and about impulse and hybrid systems are used to provide characterizations of conditional viability under impulse evolutionary games.     

Dynamic programming—neural network real-time traffic adaptive signal control algorithm

In this paper, an “intelligent” isolated intersection control system was developed. The developed “intelligent” system makes “real time” decisions as to whether to extend (and how much) current green time. The model developed is based on the combination of the dynamic programming and neural networks. Many tests show that the outcome (the extension of the green time) of the proposed neural network is nearly equal to the best solution. Practically negligible CPU times were achieved, and were thus absolutely acceptable for the “real time” application of the developed algorithm.     

A Tutorial on Computational Cluster Analysis with Applications to Pattern Discovery in Microarray Data

Microarrays offer unprecedented possibilities for the so-called omic, e.g., genomic and proteomic, research. However, they are also quite challenging data to analyze. The aim of this paper is to provide a short tutorial on the most common approaches used for pattern discovery and cluster analysis as they are currently used for microarrays, in the hope to bring the attention of the Algorithmic Community on novel aspects of classification and data analysis that deserve attention and have potential for high reward. R. Giancarlo is partially supported by Italian MIUR grants PRIN “Metodi Combinatori ed Algoritmici per la Scoperta di Patterns in Biosequenze” and FIRB “Bioinformatica per la Genomica e la Proteomica” and Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”. D. Scaturro is supported by a MIUR Fellowship in the Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”.     

Explorative and dynamic visualization of data in virtual reality

Summary  A software system has been developed for the study of dynamic glyph visualizations in the context of Visual Data Mining in Virtual Reality. The system uses parallel processing to calculate data visualizations in real-time, with real-time interaction and dynamic changes to the view. The system allows morphing between different visualizations, the use of dynamic features like “vibrations” and “rotations” of thousands of objects individually, and dynamic visualization, where the influence of any variable of a dataset with a “reasonable” distribution, can be shown as a dynamic development. It appears that these facilities for dynamic data visualization have a very promising potential, but their optimal use will depend on further developments in the context of their individual practical application.     

Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

A quadratic programming model for product configuration optimization

The various features of any product are differentially appealing to the various portions of the consumer population and have differential costs of production and marketing. This paper considers the problem of “overall product optimization”, or more specifically, “optimal product configuration”. Product price is, of course, a part of this configuration.     

Realizability of greedy algorithms

We discuss new models of an “affine” theory of gravity in multidimensional space-times with symmetric connections. We use and develop ideas of Weyl, Eddington, and Einstein, in particular, Einstein’s proposal to specify the space-time geometry by the use of the Hamilton principle. More specifically, the connection coefficients are determined using a “geometric” Lagrangian that is an arbitrary function of the generalized (nonsymmetric) Ricci curvature tensor (and, possibly, of other fundamental tensors) expressed in terms of the connection coefficients regarded as independent variables. Such a theory supplements the standard Einstein gravity with dark energy (the cosmological constant, in the first approximation), a neutral massive (or tachyonic) vector field (vecton), and massive (or tachyonic) scalar fields. These fields couple only to gravity and can generate dark matter and/or inflation. The new field masses (real or imaginary) have a geometric origin and must appear in any concrete model. The concrete choice of the geometric Lagrangian determines further details of the theory, for example, the nature of the vector and scalar fields that can describe massive particles, tachyons, or even “phantoms.” In “natural” geometric theories, which are discussed here, dark energy must also arise. We mainly focus on intricate relations between geometry and dynamics while only very briefly considering approximate cosmological models inspired by the geometric approach.     

From Hermite to stationary subdivision schemes in one and several variables

Vector and Hermite subdivision schemes both act on vector data, but since the latter one interprets the vectors as function values and consecutive derivatives they differ by the “renormalization” of the Hermite scheme in any step. In this paper we give an algebraic factorization method in one and several variables to relate any Hermite subdivision scheme that satisfies the so–called spectral condition to a vector subdivision scheme. These factorizations are natural extensions of the “zero at π” condition known for the masks of refinable functions. Moreover, we show how this factorization can be used to investigate different forms of convergence of the Hermite scheme and why the multivariate situation is conceptionally more intricate than the univariate one. Finally, we give some examples of such factorizations.     

Some linked subsets of posets

Recently Frank Tall has introduced the notion of a poset being “endowed” which is used in a forcing and reflection type proof to show that certain properties are preserved by forcing with such a poset. Subsequently Bill Fleissner introduced the property of a boolean algebra having a “lynx” and used this in an “Axiom and combinatorics” type proof of the same result. The two notions are basically the same thing. In this paper we prove that some of the usual Cohen algebras have lynxes, that it is consistent that nearly all of them have lynxes and investigate more generally the notion of lynxes. Research supported by NSERC of Canada.     

Hyperbolic balance laws: Riemann invariants and the generalized Riemann problem

The Generalized Riemann Problem (GRP) for a nonlinear hyperbolic system of m balance laws (or alternatively “quasi-conservative” laws) in one space dimension is now well-known and can be formulated as follows: Given initial-data which are analytic on two sides of a discontinuity, determine the time evolution of the solution at the discontinuity. In particular, the GRP numerical scheme (second-order high resolution) is based on an analytical evaluation of the first time derivative. It turns out that this derivative depends only on the first-order spatial derivatives, hence the initial data can be taken as piecewise linear. The analytical solution is readily obtained for a single equation (m = 1) and, more generally, if the system is endowed with a complete (coordinate) set of Riemann invariants. In this case it can be “diagonalized” and reduced to the scalar case. However, most systems with m > 2 do not admit such a set of Riemann invariants. This paper introduces a generalization of this concept: weakly coupled systems (WCS). Such systems have only “partial set” of Riemann invariants, but these sets are weakly coupled in a way which enables a “diagonalized” treatment of the GRP. An important example of a WCS is the Euler system of compressible, nonisentropic fluid flow (m = 3). The solution of the GRP discussed here is based on a careful analysis of rarefaction waves. A “propagation of singularities” argument is applied to appropriate Riemann invariants across the rarefaction fan. It serves to “rotate” initial spatial slopes into “time derivative”. In particular, the case of a “sonic point” is incorporated easily into the general treatment. A GRP scheme based on this solution is derived, and several numerical examples are presented. Special attention is given to the “acoustic approximation” of the analytical solution. It can be viewed as a proper linearization (different from the approach of Roe) of the nonlinear system. The resulting numerical scheme is the simplest (second-order, high-resolution) generalization of the Godunov scheme.     

The Betti reciprocity principle and the normal boundary component control problem for linear elastic systems

The background for this article is the question of modification of the geometric configuration of an elastic structure by means of “volume” type actuation. In this actuation mode stresses are applied to the elastic body by injection/extraction of a fluid into, or from, a large number of vacuoles in the elastic “matrix” material. Previous articles by the author, and others, have examined this process and studied its effectiveness in the context of a “naive” continuous model. The present paper continues along these lines, exploring “normal boundary component controllability” criterion for determining achievable configurations for the controlled system in the two-dimensional case. Connections with conformal mapping lead to affirmative results for approximate controllability in this sense and Fourier series techniques provide exact controllability results for the case wherein the domain of the uncontrolled system is a two-dimensional disk.      

A biomechanical inactivation principle

This paper develops the mathematical side of a theory of inactivations in human biomechanics. This theory has been validated by practical experiments, including zero-gravity experiments. The theory mostly relies on Pontryagin’s maximum principle on the one side and on transversality theory on the other side. It turns out that the periods of silence in the activation of muscles that are observed in practice during the motions of the arm can appear only if “something like the energy expenditure” is minimized. Conversely, minimization of a criterion taking into account the “energy expenditure” guaranties the presence of these periods of silence, for sufficiently short movements.     

Ranking players by “power” in weighted voting systems: The multi-relation method

A new quantitative definition of the “power index” is proposed for a voter in weighted voting systems (WV-schemes), where the voters a priori do not have equal rights. The proposed “power index” is generated in a self-consistent manner from information about the number of times that a voter enters any winning coalition in the WV-scheme. Explicit formulas are derived for computing the “power index”. The discussion is illustrated with prototype examples. __________ Translated from Prikladnaya Matematika i Informatika, No. 25, pp. 81–98, 2007.     

Quantum Backreaction (Casimir) Effect II. Scalar and Electromagnetic Fields

Casimir effect in most general terms may be understood as a backreaction of a quantum system causing an adiabatic change of the external conditions under which it is placed. This paper is the second installment of a work scrutinizing this effect with the use of algebraic methods in quantum theory. The general scheme worked out in the first part is applied here to the discussion of particular models. We consider models of the quantum scalar field subject to external interaction with “softened” Dirichlet or Neumann boundary conditions on two parallel planes. We show that the case of electromagnetic field with softened perfect conductor conditions on the planes may be reduced to the other two. The “softening” is implemented on the level of the dynamics, and is not imposed ad hoc, as is usual in most treatments, on the level of observables. We calculate formulas for the backreaction energy in these models. We find that the common belief that for electromagnetic field the backreaction force tends to the strict Casimir formula in the limit of “removed cutoff” is not confirmed by our strict analysis. The formula is model dependent and the Casimir value is merely a term in the asymptotic expansion of the formula in inverse powers of the distance of the planes. Typical behaviour of the energy for large separation of the plates in the class of models considered is a quadratic fall-of. Depending on the details of the “softening” of the boundary conditions the backreaction force may become repulsive for large separations. Communicated by Klaus Fredenhagen submitted 9/09/04, accepted 1/07/05