Michell cantilevers constructed within trapezoidal domains—Part I: geometry of Hencky nets

The present paper is the first part of the four-part work on Michell cantilevers transmitting a given point load to a given segment of a straight-line support, the feasible domain being a part of the half-plane contained between two fixed half-lines. The axial stress σ in the optimal cantilevers is assumed to be bounded by −σ _C ≤σ≤σ _T , where σ _C and σ _T represent the allowable compressive and tensile stresses, respectively. The work provides generalization of the results of the article of Lewiński et al. (Int J Mech Sci 36:375–398, 1994a) to the case of σ _T ≠σ _C . The present, first part of the work concerns the analytical formation of the Hencky nets or the lines of fibres filling up the interior of the optimal cantilevers corresponding to an arbitrary position of the point of application of the given concentrated force.     

Impurity Heat Capacity and its Relation to Entanglement in Dilute Magnetic Alloys

Using an asymptotic solution of the thermodynamics of a dilute s-d system comprising M magnetic impurities interacting with the electron gas, the impurity energy and impurity heat capacity ΔC(T) are derived for dilute magnetic alloys with spin 1/2 and spin 3/2 impurities. ΔC(T) can be viewed as a measure of entanglement between impurities and electrons in a dilute magnetic alloy. The parameters which enter ΔC are adjusted to fit experimental data on impurity heat capacity of CuCr and (La_1-x Ce _x ) Al₂. Agreement is satisfactory for CuCr, at temperatures below 1K, and good for (La_1-x Ce _x ) Al₂. The magnitude of theoretical ΔC(T) agrees with experiment and does not require scaling as in previous s-d theories. Nonlinear dependence of ΔC(T) on impurity concentration has been accounted for the first time.     

A special case of the single-machine total tardiness problem is NP-hard

In this paper, it is shown that the special case B-1 of the single-machine total tardiness problem 1 ∥ ΣT _j is NP-hard in the ordinary sense. For this case, there exists a pseudo-polynomial algorithm with run time O(n σp _j). Published in Russian in Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya, 2006, No. 3, pp. 120–128. Article was translated by the authors.     

Image Compression and Reconstruction Using pi<Subscript><Emphasis Type="Italic">t</Emphasis></Subscript>-Sigma Neural Networks

A high-order feedforward neural architecture, called pi _t -sigma (π _t σ) neural network, is proposed for lossy digital image compression and reconstruction problems. The π _t σ network architecture is composed of an input layer, a single hidden layer, and an output layer. The hidden layer is composed of classical additive neurons, whereas the output layer is composed of translated multiplicative neurons (π _t -neurons). A two-stage learning algorithm is proposed to adjust the parameters of the π _t σ network: first, a genetic algorithm (GA) is used to avoid premature convergence to poor local minima; in the second stage, a conjugate gradient method is used to fine-tune the solution found by GA. Experiments using the Standard Image Database and infrared satellite images show that the proposed π _t σ network performs better than classical multilayer perceptron, improving the reconstruction precision (measured by the mean squared error) in about 56%, on average.     

Michell cantilevers constructed within trapezoidal domains—Part II: virtual displacement fields

The present second part of the paper deals with the virtual displacement fields associated with the optimality conditions , where σ _T and σ _C represent the allowable values of the tensile and compressive stress, respectively. The displacement fields vanish along a straight segment of a line support and are constructed within an infinite domain bounded by two half-lines. The displacement fields are provided by the integral formulae involving the Lamé fields found in part I of this paper. All the results are expressed in terms of Lommel-like functions. These results make it possible to determine the volumes of the optimal cantilevers designs within the feasible domain considered. Computation of the volumes along with analyses of concrete cantilevers will be the subject of part IV of the present paper.     

Effects of actuating waveform,ink property,and nozzle size on piezoelectrically driven inkjet droplets

Computational fluid dynamics and micro-flow visualization (μ-FV) have been complementarily performed to study the evolution of a single droplet ejected from a bend-mode piezoelectric inkjet printhead. The numerical simulation is characterized by the coupled piezoelectric-structural-fluid solution procedure and verified by the μ-FV results. The in-house numerical code is subsequently applied to investigate the influences of electric voltage φ _pp, pulse shape, ink property, and nozzle diameter D _n on the droplet volume, velocity, and configurations. φ _pp studied ranges from 14 to 26 V and pulse shape is explored by varying the key time intervals with fixed voltage slopes. The influence of ink property is examined by investigating the dynamic viscosity μ and surface tension σ separately. Investigation on the effects of nozzle diameter is also conducted by decreasing D _n from 26 to 11 at 3 μm interval. The computed results are found in good agreement with the experimental ones. New findings are to discover the critical ranges of electric waveform parameters, μ, and σ outside which the phenomena of satellite droplets and puddle formation at the nozzle opening are absent. In addition, the imbedded physical rationales for these critical ranges are provided. The results are also new in terms of the identifications of the critical σ and D _n for the reference of improving the droplet quality.     

Algorithms for constrained <Emphasis Type="Italic">k</Emphasis>-nearest neighbor queries over moving object trajectories

An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (≥ 1) trajectories that lie closest to q and intersect (or are enclosed by) CR; and (ii) an HCCkNN query on trajectories retrieves the constrained k nearest neighbors (CkNNs) of q at any time instance of T. We propose a suite of algorithms for processing CkNN queries and HCCkNN queries respectively, with different properties and advantages. In particular, we thoroughly investigate two types of CkNN queries, i.e., CkNN_P and CkNN_T, which are defined with respect to stationary query points and moving query trajectories, respectively; and two types of HCCkNN queries, namely, HCCkNN_P and HCCkNN_T, which are continuous counterparts of CkNN_P and CkNN_T, respectively. Our methods utilize an existing data-partitioning index for trajectory data (i.e., TB-tree) to achieve low I/O and CPU cost. Extensive experiments with both real and synthetic datasets demonstrate the performance of the proposed algorithms in terms of efficiency and scalability.     

Stability Analysis of an Endoreversible Heat Engine with Stefan-Boltzmann Heat Transfer Law Working in Maximum-Power-Like Regime

A local stability study of an endoreversible Stefan-Boltzmann (SB) engine, working in a maximum-power-like regime, is presented. This engine consists of a Carnot engine that exchanges heat with heat reservoirs T1 and T2, (T1 > T2) through a couple of thermal links, both having the same conductance g. In addition, the working fluid has the same heat capacity C in the two isothermal branches of the cycle. From the local stability analysis we conclude that the SB engine is stable for every value of g, C and τ = T2/T1. After a small perturbation, the system decays to the steady state with either of two different relaxation times; both being proportional to C/g, and τ. Finally, when we plot some of the thermodynamic properties in the steady state versus τ, we find how an increment of τ can improve the stability of the system, at the same decreasing the efficiency and the power of the system. This suggests a compromise between the stability and the energetic properties of the engine driven by τ.     

Explaining the lazy Krivine machine using explicit substitution and addresses

In a previous paper, Benaissa, Lescanne, and Rose, have extended the weak lambda-calculus of explicit substitution λ σ _w with addresses, so that it gives an account of the sharing implemented by lazy functional language interpreters. We show in this paper that their calculus, called λ σ _w ^a , fits well to the lazy Krivine machine, which describes the core of a lazy (call-by-need) functional programming language implementation. The lazy Krivine machine implements term evaluation sharing, that is essential for efficiency of such languages. The originality of our proof is that it gives a very detailed account of the implemented strategy.     

Steiner Trees in General Nonuniform Orientations

In this paper we consider Steiner minimum trees (SMT) in the plane, where the connections can only be along a given set of fixed but arbitrary (not necessarily uniform) orientations. The orientations define a metric, called the general orientation metric, A _σ, where σ is the number of orientations. We prove that in A _σ metric, there exists an SMT whose Steiner points belong to an (n−2)-level grid. This result generalizes a result by Lee and Shen [11], and a result by Du and Hwang [5]. In the former case, the same result was obtained for the special case when all orientations are uniform, while in the latter case the same result was proven for the special case when there are only three arbitrary orientations. We then modify the proof used in the main result for the special case when σ=3, i.e., only three arbitrary orientations are considered, and obtain a better result, which states that there exists an SMT whose Steiner points belong to an -level grid. The result has also been obtained by Lin and Xue [9] using a different approach. Received September 27, 1999; revised August 14, 2000     

Generalized multiagent learning with performance bound

We present new Multiagent learning (MAL) algorithms with the general philosophy of policy convergence against some classes of opponents but otherwise ensuring high payoffs. We consider a 3-class breakdown of opponent types: (eventually) stationary, self-play and “other” (see Definition 4) agents. We start with ReDVaLeR that can satisfy policy convergence against the first two types and no-regret against the third, but it needs to know the type of the opponents. This serves as a baseline to delineate the difficulty of achieving these goals. We show that a simple modification on ReDVaLeR yields a new algorithm, RV _σ(t), that achieves no-regret payoffs in all games, and convergence to Nash equilibria in self-play (and to best response against eventually stationary opponents—a corollary of no-regret) simultaneously, without knowing the opponent types, but in a smaller class of games than ReDVaLeR . RV _σ(t) effectively ensures the performance of a learner during the process of learning, as opposed to the performance of a learned behavior. We show that the expression for regret of RV _σ(t) can have a slightly better form than those of other comparable algorithms like GIGA and GIGA-WoLF though, contrastingly, our analysis is in continuous time. Moreover, experiments show that RV _σ(t) can converge to an equilibrium in some cases where GIGA, GIGA-WoLF would fail, and to better equilibria where GIGA, GIGA-WoLF converge to undesirable equilibria (coordination games). This important class of coordination games also highlights the key desirability of policy convergence as a criterion for MAL in self-play instead of high average payoffs. To our knowledge, this is also the first successful (guaranteed) attempt at policy convergence of a no-regret algorithm in the Shapley game.     

Measures on MV-algebras

 We study sequentially continuous measures on semisimple M V-algebras. Let A be a semisimple M V-algebra and let I be the interval [0,1] carrying the usual Łukasiewicz M V-algebra structure and the natural sequential convergence. Each separating set H of M V-algebra homomorphisms of A into I induces on A an initial sequential convergence. Semisimple M V-algebras carrying an initial sequential convergence induced by a separating set of M V-algebra homomorphisms into I are called I-sequential and, together with sequentially continuous M V-algebra homomorphisms, they form a category SM(I). We describe its epireflective subcategory ASM(I) consisting of absolutely sequentially closed objects and we prove that the epireflection sends A into its distinguished σ-completion σ _H (A). The epireflection is the maximal object in SM(I) which contains A as a dense subobject and over which all sequentially continuous measures can be continuously extended. We discuss some properties of σ _H (A) depending on the choice of H. We show that the coproducts in the category of D-posets [9] of suitable families of I-sequential M V-algebras yield a natural model of probability spaces having a quantum nature. The motivation comes from probability: H plays the role of elementary events, the embedding of A into σ _H (A) generalizes the embedding of a field of events A into the generated σ-field σ(A), and it can be viewed as a fuzzyfication of the corresponding results for Boolean algebras in [8, 11, 14]. Sequentially continuous homomorphisms are dual to generalized measurable maps between the underlying sets of suitable bold algebras [13] and, unlike in the Loomis–Sikorski Theorem, objects in ASM(I) correspond to the generated tribes (no quotient is needed, no information about the elementary events is lost). Finally, D-poset coproducts lift fuzzy events, random functions and probability measures to events, random functions and probability measures of a quantum nature. Supported by VEGA Grant 2/7193/01     

Polynomial Time Introreducibility

Abstract. We introduce the polynomial time version, in short ≤ ^P _T -introreducibility, of the notion of introreducibility studied in Recursion Theory. We give a simpler proof of the known fact that a set is ≤ ^P _T -introreducible if and only if it is in P. Our proof generalizes to virtually all the computation bounded reducibilities ≤ _r , showing that a set is ≤ _r -introreducible if and only if it belongs to the minimum ≤ _r -degree. It also holds for most unbounded reducibilities like ≤ _m , ≤ _c , ≤ _d , ≤ _p , ≤ _tt , etc., but it does not hold for ≤ _T . A very strong way for a set L to fail being ≤ _r -introreducible is that L is not ≤ _r -reducible to any coinfinite subset of L . We call such sets ≤ _r -introimmune. It is known that ≤ _T -introimmune sets exist but they are not arithmetical. In this paper we ask for which reducibilities ≤ _r there exist arithmetical ≤ _r -introimmune sets. We show that they exist for the reducibilities ≤ _c and ≤ ^N _m . Finally, we prove separation results between introimmunities.     

Generating Combinations by Three Basic Operations

We investigate the problem of listing combinations using a special class of operations, prefix shifts. Combinations are represented as bitstrings of O＇s and l＇s, and prefix shifts are the operations of rotating some prefix of a bitstring by one position to left or right. We give a negative answer to an open problem asked by F. Ruskey and A. Williams （Generating combinations by prefix shifts, In Proc. llth Annual International Computing and Combinatorics Conference 2005, LNCS 3595, Springer, 2005, pp.570-576）, that is whether we can generate combinations by only using three very basic prefix shifts on bitstrings, which are transposition of the first two bits and the rotation of the entire bitstring by one position in either direction （i.e., applying the permutations σ2, σn and σn^-1 to the indices of the bitstrings）.     

Approximation Algorithms for Bounded Degree Phylogenetic Roots

The Degree- Δ Closest Phylogenetic k th Root Problem (ΔCPR _k ) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E ⊕{{u,v} : u,v are leaves of T and d _T (u,v)≤k}|, is minimized, where d _T (u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for Δ CPR ₂ for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR ₃, and a polynomial-time approximation scheme for the maximization version of Δ CPR _k for any fixed Δ and k.     

Implementing mapping composition

Mapping composition is a fundamental operation in metadata driven applications. Given a mapping over schemas σ₁ and σ₂ and a mapping over schemas σ₂ and σ₃, the composition problem is to compute an equivalent mapping over σ₁ and σ₃. We describe a new composition algorithm that targets practical applications. It incorporates view unfolding. It eliminates as many σ₂ symbols as possible, even if not all can be eliminated. It covers constraints expressed using arbitrary monotone relational operators and, to a lesser extent, non-monotone operators. And it introduces the new technique of left composition. We describe our implementation, explain how to extend it to support user-defined operators, and present experimental results which validate its effectiveness. T.J. Green and A. Nash’s work was performed during an internship at Microsoft Research. A preliminary version of this work was published in the VLDB 2006 conference proceedings.     

Minimizing total tardiness on parallel machines with preemptions

The basic scheduling problem we are dealing with in this paper is the following one. A set of jobs has to be scheduled on a set of parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement and arbitrary due dates. Each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. The goal is to find a schedule that minimizes the sum of tardiness, i.e., we consider problem Q∣r _j ,p _j =p, pmtn∣∑T _j whose complexity status was open. Recently, Tian et al. (J. Sched. 9:343–364, 2006) proposed a polynomial algorithm for problem 1∣r _j ,p _j =p, pmtn∣∑T _j . We show that both the problem P∣ pmtn∣∑T _j of minimizing total tardiness on a set of parallel machines with allowed preemptions and the problem P∣r _j ,p _j =p, pmtn∣∑T _j of minimizing total tardiness on a set of parallel machines with release dates, equal processing times and allowed preemptions are NP-hard. Moreover, we give a polynomial algorithm for the case of uniform machines without release dates, i.e., for problem Q∣p _j =p, pmtn∣∑T _j .     

A generalized distribution model for random recursive trees

 A random tree T _n of order n is constructed by choosing in a random tree T _n-1 of order n−1 a vertex at random and connecting it to a new vertex labeled n. In the usual constraint we assume that the n−1 vertices of T _n-1 are equally likely to be chosen. We introduce and research a more general case in which a distribution of choosing vertices is defined by a sequence α₁, α₂, …. Received: 14 February 1995/2 January 1996     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.