Computing Vertex Connectivity: New Bounds from Old Techniques

The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ³ + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ₁nmlog(n²/m)) where κ₁ ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n²/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity.     

Higher order representations of the Robbins–Monro process

For quasi-linear regression functions, the Robbins–Monro process X_n is decomposed in a sum of a linear form and a quadratic form both defined in the observation errors. Under regularity conditions, the remainder term is of order O(n^−3/2) with respect to the L_p-norm. If a cubic form is added, the remainder term can be improved up to an order of O(n⁻²). As a corollary the expectation of X_n is expanded up to an error of order O(n⁻²). This is used to correct the bias of X_n up to an error of order O(n^−3/2 log n).     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

On Parallel Complexity of Nonsmooth Convex Optimization

We consider the standard class of problems ƒ(x) → min, x B_n associated with convex continuous functions ƒ mapping the unit n-dimensional cube B_n into [0, 1]. It is known that the information complexity of the class with respect to the standard first-order oracle is, within an absolute constant factor, n ln (1/ε), ε < being the required accuracy (measured in terms of ƒ). The question we are interested in is how the complexity can be reduced if one is allowed to use K copies of the oracle in parallel rather than a single oracle. We demonstrate that the "K-oracle complexity" is at least O(1)(n/ln(2Kn))^1/3ln(1/ε).     

Spinel fibers for ceramics

The process of formation of a fibrous spinel in the Al₂O₃–MgO system is investigated. The dependences of the spinel structure and properties on technological parameters of the process of synthesis is studied. Optimal relations between the fiber constituents for obtaining a stoichiometric spinel are determined and a two-stage mechanism of its formation has been found. Some ceramic materials are obtained from fibrous dispersions, and their physicomechanical characteristics have been estimated.Institute of General and Inorganic Chemistry, Belarus National Academy of Sciences, Minsk, Belarus. Translated from Mekhanika Kompozitnykh Materialov, Vol. 35, No. 4, pp. 509–516, July–August, 1999.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

Structure and properties of ceramic composites based on ZrO2

Monodisperse fine powders of high purity obtained by sol-gel method are used for production of high technical data ceramics. The fiber reinforcement is used for hardening of composite materials. It was of interest to study production possibility of reinforced composite material based on ZrO₂ obtained by sol-gel method with filler from fibers of partially stabilized zirconia. ZrO₂ powders were obtained by precipitation of its hydrated gel from aqueous zirconium oxychloride solution by ammonium hydroxide followed by thermal treatment. For composite reinforcement ceramic partially stabilized (8 mole Y₂O₃) ZrO₂ fibers 0.16–0.67 mm in length and 5–7 m in diameter were used. Content of the fibers in composite was 20 wt.%. From powders and their mixtures with fibers, the samples were pressed as disks, beams and cylinders, and anneal in air at 1100–1600°C temperature range. The investigation has shown that the fibers of partially stabilized zirconia change the composite structure, increase the content of tetragonal modification that promotes its hardening. Treatment temperature of precursor determines physical chemical properties of compositions with fibers. Their high specific surface and reaction ability provides a workability of forming and sintering processes into strong composite material. The ceramics was increased by 2.5–3 times as strength after fibrous filler introduction into ZrO₂ hydrogel matrix.Presented at the Ninth International Conference on the Mechanics of Composite Materials (Riga, October 1995).Presented at the Ninth International conference on the Mechanics of Composite Materials (Riga, October 1995). Institute of General and Inorganic Chemistry of the Academy Sciences of the Belarus. Minsk. Translated from Mekhanika Kompozitnykh Materialov, Vol. 32, No. 3, pp. 418–427, May–June. 1996.     

Structure and Properties of Electrodeposited Composite Metal–Nanodisperse Inorganic Compound Coatings

By using the electrodeposition method, composite Sn-inorganic coatings have been obtained. As the inorganic compounds, ultrafine PbMo₆S₈, NbC_xN_y, Ti_xN_y, and Ti_0.63Nb_0.34C_0.38N_0.58 powders were utilized. The Sn–PbMo₆S₈ coatings containing 28-88 wt.% PbMo₆S₈ were superconductive. The highly electroconductive Sn–NbC_xN_y coatings containing 1-88 wt.% of the disperse phase and the Sn–Ti_xN_y coatings with 42-70 wt.% Ti_xN_y were structurally stable at a low temperature (–50°C), solderable, and corrosion resistant on copper. The formation of the structure of the coatings is determined by the electrolyte composition, the cathode current density during the electrolysis, and the codeposition of the disperse phase. By electrodeposition of the chromium carbonitride Cr₃C_1.6N_0.4, in the presence of H₄P₂O₇ in an CrO₃-based electrolyte, mat composite Cr–Cr₃C_1.6N_0.4 coatings with 6.8 wt.% Cr₃C_1.6N_0.4 were obtained, which had a finely uneaven surface structure. Such surfaces are needed in the cases where lubricants are used.     

Distribution of integral points on certain two-sheeted hyperboloids

Yu. V. Linnik's investigations [Vestn. Leningr. Univ., No. 2, 3–23; No. 5, 3–32; No. 8, 15–27 (1955)] are refined and generalized to indefinite ternary quadratic forms of a sufficiently general form (to forms contained in the form x₁x₃—x ₂ ² ]. The method of investigation is improved. The presentation is substantially simplified.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 93, pp. 87–141, 1980.     

Analysis of Carry Propagation in Addition: An Elementary Approach

Our goal in this paper is to analyze carry propagation in addition using only elementary methods (that is, those not involving residues, contour integration, or methods of complex analysis). Our results concern the length of the longest carry chain when two independent uniformly distributed n-bit numbers are added. First, we show using just first- and second-moment arguments that the expected length C_n of the longest carry chain satisfies C_n = log₂n + O(1). Second, we use a sieve (inclusion–exclusion) argument to give an exact formula for C_n. Third, we give an elementary derivation of an asymptotic formula due to Knuth, C_n = log₂n + Φ(log₂ n) + O((logn)⁴/n), where Φ(ν) is a bounded periodic function of ν, with period 1, for which we give both a simple integral expression and a Fourier series. Fourth, we give an analogous asymptotic formula for the variance V_n of the length of the longest carry chain: V_n = Ψ(log₂ n) + O((logn)⁵/n), where Ψ(ν) is another bounded periodic function of ν, with period 1. Our approach can be adapted to addition with the “end-around” carry that occurs in the sign-magnitude and 1s-complement representations. Finally, our approach can be adapted to give elementary derivations of some asymptotic formulas arising in connection with radix-exchange sorting and collision-resolution algorithms, which have previously been derived using contour integration and residues.     

Damped Oscillatory Integrals and the Boundedness Problem for Maximal Operators

Let S ⊂ ℝR ^{n +1} be a real-analytic hypersurface with surface measure dσ, and let ψ be a smooth nonnegative compactly supported cutoff function. Consider the surface measure dμ _q = ψ|Λ(X)|^q dσ, where Λ(X) is a damping factor determined by the matrices of the first and second fundamental forms of the surface. We show that its Fourier transform decays for large |ξ| as O (|ξ|^−(1/2+ε)), ε > 0, provided that q > 3/2. We also consider applications involving maximal operators associated with means of functions over hypersurfaces.__________Translated from Funktsional’nyi Analiz i Ego Prilozheniya, Vol. 39, No. 2, pp. 70–74, 2005Original Russian Text Copyright © by I. A. Ikromov     

Exact Misclassification Probabilities for Plug-In Normal Quadratic Discriminant Functions: II. The Heterogeneous Case

We consider the problem of discriminating between two independent multivariate normal populations, N_p(μ₁, Σ₁) and N_p(μ₂, Σ₂), having distinct mean vectors μ₁ and μ₂ and distinct covariance matrices Σ₁ and Σ₂. The parameters μ₁, μ₂, Σ₁, and Σ₂ are unknown and are estimated by means of independent random training samples from each population. We derive a stochastic representation for the exact distribution of the “plug-in” quadratic discriminant function for classifying a new observation between the two populations. The stochastic representation involves only the classical standard normal, chi-square, and F distributions and is easily implemented for simulation purposes. Using Monte Carlo simulation of the stochastic representation we provide applications to the estimation of misclassification probabilities for the well-known iris data studied by Fisher (Ann. Eugen.7 (1936), 179–188); a data set on corporate financial ratios provided by Johnson and Wichern (Applied Multivariate Statistical Analysis, 4th ed., Prentice–Hall, Englewood Cliffs, NJ, 1998); and a data set analyzed by Reaven and Miller (Diabetologia16 (1979), 17–24) in a classification of diabetic status.     

Failure of water-filled cylindrical glass-reinforced epoxy shells under internal impulsive loading

Conclusions 1. The explosive failure of water-filled, geometrically similar glass-reinforced epoxy shells, whose dimensions increase by a factor of 1.5–4.4, is not associated with an energetic scale effect. This is attributable to the imperfect similarity of the shells, since although their dimensions changed, the diameter of the glass reinforcing fibers remained the same.2. The relative mass of explosive required to fracture the shells is approximately 0.4%. With respect to this index, glass-reinforced epoxy is comparable to structural steels 20 and 17Mn1Si at R₀160 mm.3. The circumferential deformation of the shells at failure is about 4% and does not depend on the thickness of the shell wall, the dimensions of geometrically similar shells, or the initial strain rate on the interval 0.21 · 10³–1.2 · 10³ sec^–1. Thin-walled shells begin to fail from the outside surface, thick-walled shells from the inside surface.4. The modulus of elasticity of the GRE is 2.4 · 10⁵ kgf/cm² and does not depend on the strain rate on the interval 10^–3–1.5 · 10³ sec^–1. The material deforms elastically up to failure.Moscow. Translated from Mekhanika Polimerov, No. 2, pp. 283–289, March–April, 1978.     

Polyethylene with improved environmental stress cracking resistance

The stress cracking resistance of low-pressure polyethylene can be improved by introducing finely dispersed mineral additives (TiO₂, SiO₂, Al₂O₃ · SiO₂) and surface-active agents (anthranilic, adipic, and sebacic acids; mannitol). The amounts needed to effectively increase the cracking resistance without detriment to the principal physicomechanical and other characteristics of the material have been determined.Mekhanika Polimerov, Vol. 4, No. 1, pp. 67–71, 1968Communication V of the series "Modification of the Structure and Properties of Polyolefins."     

4n − 10

We show that the maximal number K₂(n) of splits in a 2-compatible split system on an n-set is exactly 4n – 10, for every n > 3.Since K₂(n) = CF₃(n)/2 where CF₃(n) is the maximal number of members in any 3-cross-free collection of (proper) subsets of an n-set, this gives a definitive answer to a question raised in 1979 by A. Karzanov who asked whether CF₃(n) is, as a function of n, of type O(n).Karzanovs question was answered first by P. Pevzner in 1987 who showed K₂(n) 6n, a result that was improved by T. Fleiner in 1998 who showed K₂(n) 5n.The argument given in the paper below establishes that the even slightly stronger inequality K₂(n) 4n – 10 holds for every n > 3; the identity K₂(n) = 4n – 10 (n > 3) then follows in conjunction with a result from a previous paper that implies K₂(n) 4n – 10. In that paper, it was also mentioned that—in analogy to well known results regarding maximal weakly compatible split systems—2-compatible split systems of maximal cardinality 4n – 10 should be expected to be cyclic. Luckily, our approach here permits us also to corroborate this expectation. As a consequence, it is now possible to generate all 2-compatible split systems on an n-set (n > 3) that have maximal cardinality 4n – 10 (or, equivalently, all 3-cross-free set systems that have maximal cardinality 8n – 20) in a straight forward, systematic manner.Received March 19, 2003     

Stability of a Pivoting Strategy for Parallel Gaussian Elimination

Gaussian elimination with partial pivoting achieved by adding the pivot row to the kth row at step k, was introduced by Onaga and Takechi in 1986 as means for reducing communications in parallel implementations. In this paper it is shown that the growth factor of this partial pivoting algorithm is bounded above by _n <#60; 3 ^n–1, as compared to 2 ^n–1 for the standard partial pivoting. This bound _n, close to 3 ^n–2, is attainable for class of near-singular matrices. Moreover, for the same matrices the growth factor is small under partial pivoting.This revised version was published online in October 2005 with corrections to the Cover Date.     

The complexity of finding generalized paths in tournaments

Given a tournament with n vertices, we consider the number of comparisons needed, in the worst case, to find a permutation υ₁υ₂…υ_n of the vertices, such that the results of the games υ₁υ₂, υ₂υ₃,…, υ_n−1υ_n match a prescribed pattern. If the pattern requires all arcs to go forwrd, i.e., υ₁ → υ₂, υ₂ → υ₃,…, υ_n−1 → υ_n, and the tournament is transitive, then this is essentially the problem of sorting a linearly ordered set. It is well known that the number of comparisons required in this case is at least cn lg n, and we make the observation that O(n lg n) comparisons suffice to find such a path in any (not necessarily transitive) tournament. On the other hand, the pattern requiring the arcs to alternate backward-forward-backward, etc., admits an algorithm for which O(n) comparisons always suffice. Our main result is the somewhat surprising fact that for various other patterns the complexity (number of comparisons) of finding paths matching the pattern can be cn lg^αn for any α between 0 and 1. Thus there is a veritable spectrum of complexities, depending on the prescribed pattern of the desired path. Similar problems on complexities of algorithms for finding Hamiltonian cycles in graphs and directed graphs have been considered by various authors, [2, pp. 142, 148, 149; 4].     

Integrable Hierarchy, 3×3 Constrained Systems, and Parametric Solutions

This paper provides a new integrable hierarchy. The DP equation: m _t +um _x +3mu _x =0, m=u–u _xx , proposed recently by Degasperis and Procesi, is the first member in the negative order hierarchy while the first equation in the positive order hierarchy is: m _t =4(m ^–2/3) _x –5(m ^–2/3) _xxx +(m ^–2/3) _xxxxx . The whole hierarchy is shown Lax-integrable through solving a key matrix equation. To obtain the parametric solutions for the whole hierarchy, we separately discuss the negative order and the positive order hierarchies. For the negative order hierarchy, its 3×3 Lax pairs and corresponding adjoint representations are cast in Liouville-integrable Hamiltonian canonical systems under the Dirac–Poisson bracket defined on a symplectic submanifold of R ^6N . Based on the integrability of those finite-dimensional canonical Hamiltonian systems we give the parametric solutions of all equations in the negative order hierarchy. In particular, we obtain the parametric solution of the DP equation. Moreover, for the positive order hierarchy, we consider a different constraint and process a procedure similar to the negative case to obtain the parametric solutions of the positive order hierarchy. In a special case, we give the parametric solution of the 5th-order PDE m _t =4(m ^–2/3) _x –5(m ^–2/3) _xxx +(m ^–2/3) _xxxxx . Finally, we discuss the stationary solutions of the 5th-order PDE, which may be included in the parametric solution.     

Stable minimum space partitioning in linear time

In the stable0–1 sorting problem the task is to sort an array ofn elements with two distinct values such that equal elements retain their relative input order. Recently, Munro, Raman and Salowe gave an algorithm which solves this problem inO(n log*n) time and constant extra space. We show that by a modification of their method the stable0–1 sorting is possible inO(n) time andO(1) extra space. Stable three-way partitioning can be reduced to stable0–1 sorting. This immediately yields a stable minimum space quicksort, which sorts multisets in asymptotically optimal time with high probability.