On the uniform edge-partition of a tree

We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k?n. The objective is to minimize the ratio of the maximum to the minimum number of edges of the subgraphs in the partition. We show that, for any tree and k?4, there exists a k-split with ratio at most two. For general k, we propose a simple algorithm that finds a k-split with ratio at most three in O(nlogk) time. Experimental results on random trees are also shown.     

On the distribution of the ratio of the largest eigenvalue to the trace of a Wishart matrix

The ratio of the largest eigenvalue divided by the trace of a p×p random Wishart matrix with n degrees of freedom and an identity covariance matrix plays an important role in various hypothesis testing problems, both in statistics and in signal processing. In this paper we derive an approximate explicit expression for the distribution of this ratio, by considering the joint limit as both p,n→∞ with p/n→c. Our analysis reveals that even though asymptotically in this limit the ratio follows a Tracy-Widom (TW) distribution, one of the leading error terms depends on the second derivative of the TW distribution, and is non-negligible for practical values of p, in particular for determining tail probabilities. We thus propose to explicitly include this term in the approximate distribution for the ratio. We illustrate empirically using simulations that adding this term to the TW distribution yields a quite accurate expression to the empirical distribution of the ratio, even for small values of p,n.     

A tight bound on the min-ratio edge-partitioning problem of a tree

In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree T with n edges and a positive integer k≤n, we design an algorithm to partition T into k edge-disjoint subtrees such that the ratio of the maximum number to the minimum number of edges of the subtrees is at most two. The best previous upper bound of the ratio is three, given by Wu et al. [B.Y. Wu, H.-L. Wang, S.-T. Kuan, K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics 155 (10) (2007) 1213-1223]. Wu et al. also showed that for some instances, it is impossible to achieve a ratio better than two. Therefore, there is a lower bound of two on the ratio. It follows that the ratio upper bound attained in this paper is already tight.     

Free molecular flow past a flat plate in the presence of a nontrivial gas-surface interaction

Aerodynamic forces acting on a flat plate, placed in a uniform free molecular flow, are investigated by means of a non trivial gas-surface interaction model proposed by the authors. Drag and lift coefficients and lift to drag ratio are calculated for a large number of values of some meaningful parameters, such as the speed ratio, the gas-wall temperature ratio, the attack angle and two coefficients contained in the reemission model. Simple analytical expressions, different from the classical ones, are obtained for very high or very low speed ratio values.

---

Riassunto Le forze aerodinamiche agenti su una lastra piana, posta in una corrente uniforme di gas in regime di molecole libere, sono studiate per mezzo di un modello non banale di interazione gas-superficie solida, già proposta dagli autori. I coefficienti di resistenza e di portanza e il rapporto tra queste due quantità sono calcolati per un notevole numero di valori assegnati ad alcuni parametri significativi, come il rapporto di velocità, il rapporto tra temperatura del gas e della parete, l'angolo di attacco e due coefficienti propri del modello di riemissione. Per velocità molto alte o molto piccole si forniscono delle espressioni analitiche esplicite, differenti da quelle ricavabili dalla teoria classica dei coefficienti di accomodamento.

     

A Note on the Approximation of a Minimum-Weight Maximal Independent Set

We consider the polynomial approximation behavior of the problem of finding, in a graph with weighted vertices, a maximal independent set minimizing the sum of the weights. In the spirit of a work of Halldórson dealing with the unweighted case, we extend it and perform approximation hardness results by using a reduction from the minimum coloring problem. In particular, a consequence of our main result is that there does not exist any polynomial time algorithm approximating this problem within a ratio independent of the weights, unless P = NP. We bring also to the fore a very simple ratio guaranteed by every algorithm while no polynomial time algorithm can guarantee the ratio (1 – ). The known hardness results for the unweighted case can be deduced. We finally discuss approximation results for both weighted and unweighted cases: we perform an approximation ratio that is valid for any algorithm for the former and propose an analysis of a greedy algorithm for the latter.     

On a certain geometric mean of the values of a polynomial

The maximum of the geometric mean of the values of a polynomial in the vertices of a regularkgon inscribed into the unit circle is greater than or equal to its Mahler measure. It also tends to the Mahler measure ask tends to infinity. We give quantitative versions of this statement: the upper bounds for the ratio of these two quantities. Partially supported by the Lithuanian State Science and Studies Foundation. Published in Lietuvos Matematikos Rinkinys, Vol. 40, No. 1, pp. 17–27, January–March, 2000.     

A note on the minimum bounded edge-partition of a tree

Minimum bounded edge-partition divides the edge set of a tree into the minimum number of disjoint connected components given a maximum weight for any component. It is an adaptation of the uniform edge-partition of a tree. An optimization algorithm is developed for this NP-hard problem, based on repeated bin packing of inter-related instances. The algorithm has linear running time for the class of ‘balanced trees’ common for the stochastic programming application which motivated investigation of this problem.Fast 2-approximation algorithms are formed for general instances by replacing the optimal bin packing with almost any bin packing heuristic. The asymptotic worst-case ratio of these approximation algorithms is never better than the absolute worst-case ratio of the bin packing heuristic used.     

On the motion of a fluid in a curved pipe of elliptical cross-section

Summary The motion of an incompressible viscous fluid in a curved pipe of elliptic cross-section is examined. The flux ratio in this pipe and in a straight pipe of elliptic cross-section has been evaluated under the same pressure conditions.

---

Zusammenfassung Die vorliegende Arbeit untersucht die Strömung einer inkompressiblen, zähen Flüssigkeit durch ein gekrümmtes Rohr mit elliptischem Querschnitt. Das Verhältnis des Durchflusses in diese Rohr und durch ein geradliniges Rohr von elliptischem Querschnitt unter demselben Druckgefälle wurde berechnet.

     

The type and stable type of the boundary of a Gromov hyperbolic group

Consider an ergodic non-singular action \(\Gamma \curvearrowright B\) of a countable group on a probability space. The type of this action codes the asymptotic range of the Radon–Nikodym derivative, also called the ratio set. If \(\Gamma \curvearrowright X\) is a pmp (probability-measure-preserving) action, then the ratio set of the product action \(\Gamma \curvearrowright B\times X\) is contained in the ratio set of \(\Gamma \curvearrowright B\) . So we define the stable ratio set of \(\Gamma \curvearrowright B\) to be the intersection over all pmp actions \(\Gamma \curvearrowright X\) of the ratio sets of \(\Gamma \curvearrowright B\times X\) . By analogy, there is a notion of stable type which codes the stable ratio set of \(\Gamma \curvearrowright B\) . This concept is crucially important for the identification of the limit in pointwise ergodic theorems established by the author and Amos Nevo. Here, we establish a general criteria for a nonsingular action of a countable group on a probability space to have stable type \(III_\lambda \) for some \(\lambda >0\) . This is applied to show that the action of a non-elementary Gromov hyperbolic group on its boundary with respect to a quasi-conformal measure is not type \(III_0\) and, if it is weakly mixing, then it is not stable type \(III_0\) .     

On the ‘confidence bounds” of the ratio of the means of a bivariate normal distribution

Summary Although the “confidence bounds’ of the ratio of the means of a bivariate normal distribution given by R. A. Fisher in his bookStatistical Methods for Research Workers is not the confidence bounds in the strict sense of the words, it is shown in the present article that they can be regarded as confidence bounds in a certain subset of parameter space.     

Variation of Poisson's ratio in the course of a complete one-dimensional creep cycle

By solving the system of differential equations of a standard solid, expressions are obtained for determining Poisson's ratio with allowance for the characteristics of volume and shear strain. For a material having values of Poisson's ratio in creep (0)<0.5 and ()=0.5, Poisson's ratio in reverse creep (t)^rev>0.5. The volume strains that occur at the beginning of reverse creep have the same magnitude as the creep volume strains, but the opposite sign. The law of disappearance of the volume strains is the same for creep and reverse creep.Mekhanika Polimerov, Vol. 4, No. 2, pp. 227–231, 1968     

The ratio set of the harmonic measure of a random walk on a hyperbolic group

We consider the harmonic measure on the Gromov boundary of a non-amenable hyperbolic group defined by a finite range random walk on the group, and study the corresponding orbit equivalence relation on the boundary. It is known to be always amenable and of type III. We determine its ratio set by showing that it is generated by certain values of the Martin kernel. In particular, we show that the equivalence relation is never of type III₀.     

The disteribution of a moment estimator for a parameter of the generalized poision distribution

The ratio of the sample variance to the sample mean estimates a simple function of the parameter which measures the departure of the Poisson-Poisson from the Poisson distribution. Moment series to order n²⁴ are given for related estimators. In one case, exact integral formulations are given for the first two moments, enabling a comparison to be made between their asymptotic developments and a computer-oriented extended Taylor series (COETS) algorithm. The integral approach using generating functions is sketched out for the third and fourth moments. Levin's summation algorithm is used on the divergent series and comparative simulation assessments are given.     

Global asymptotic stability and a property of the SIS model on bipartite networks

In this paper, we study an SIS model on bipartite networks, in which the network structure and a connectivity-dependent infection scheme are considered. Applying the theory of the multigroup model, we prove the existence and the asymptotic stability of the endemic equilibrium. And then we examine the ratio between the densities of infected female and male individuals on the bipartite networks. In particular, we find that when the scale exponent (γ_F) of females is equal to and that of males (γ_M), the ratio is only determined by the scale exponents and the proportion between the infection rates of females and males (λ_F/λ_M). We also present a result for the ratio by numerical simulations when γ_F≠γ_M.     

Minimizing the total completion time on-line on a single machine, using restarts

We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e−1)≈1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.     

Classification of a family of symmetric graphs with complete 2-arc-transitive quotients

In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs.     

Approximability results for the resource-constrained project scheduling problem with a single type of resources

In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(logn), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(logn), and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to $O(\sqrt{n})$ , and known lower bounds have a relative error of at least equal to O(logn). This type of instances corresponds to the single machine parallel-batch scheduling problem 1|p?batch,b=∞|C _max.     

On the circles of Apollonius associated with a triangle

Given a ratio , >>0, and a triangle ABC, on the sides and , using ratios , and , three circles of Apollonius are denned. In this paper, we will show that the three centers are collinear, the circles are coaxal and develop a necessary and sufficient condition that these circles intersect. J. A. Hoskins, W. D. Hoskins and R. G. Stanton obtained these results in a recent paper using algebraic computation. Our aim is to establish all these results using only results from elementary Euclidean geometry and thereby uncovering more geometric insights and avoid lengthy calculations.     

Investigation of the Poisson's ratio of certain crystalline polymers under a constant compressive load

The results of an investigation of the Poisson's ratio in compression for two crystalline polymers, low-density polyethylene and teflon, are given. The effect of time under load and temperature on the value of the Poisson's ratio is examined.Mekhanika Polimerov, Vol. 1, No. 4, pp. 43–46, 1965     

An O(n) algorithm to find a near-optimum partition of a convex polygon

This paper presents a heuristic algorithm to partition an n-sided convex polygon into n ? 2 nonintersecting triangles. Based on some theorems in [T. C. Hu and M. T. Shing, to appear], we can give a general formula to find the maximum ratio between the cost of the heuristic partition and the cost of the optimum partition and prove that this ratio never exceeds 1.155. We also given an example to show that the bound is tight.