A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

A note on the three color problem

It is shown that a planar graph withouti-circuits, 4 i 9, is 3-colorable. This result strengthens the result obtained by H.L. Abbott and B. Zhou.The author's research was partially supported by the Office of Naval Research, Grant number N00014-92-J-1965.     

An analysis of the composite step biconjugate gradient method

Summary The composite step biconjugate gradient method (CSBCG) is a simple modification of the standard biconjugate gradient algorithm (BCG) which smooths the sometimes erratic convergence of BCG by computing only a subset of the iterates. We show that 2×2 composite steps can cure breakdowns in the biconjugate gradient method caused by (near) singularity of principal submatrices of the tridiagonal matrix generated by the underlying Lanczos process. We also prove a best approximation result for the method. Some numerical illustrations showing the effect of roundoff error are given.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contracts N00014-90-J-1695 and N00014-92-J-1890, the Department of Energy under, contract DE-FG03-87ER25307, the National Science Foundation under contracts ASC 90-03002 and ASC 92-01266, and the Army Research Office under contract DAAL03-91-G-0150. Part of this work was completed during a visit to the Computer Science Dept. The Chinese University of Hong Kong.     

On-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Symplectic structure and reduction on the space of Riemannian metrics

The space of Riemannian metrics ${\mathfrak{Met}}MThe space of Riemannian metrics on an oriented compact manifold M of dimension n = 4k − 2 is endowed with a canonical presymplectic structure and a moment map [cf. Ferreiro Pérez and Mu?oz Masqué, Preprint (arXiv: math.DG/0507075)]. The fiber is characterized as the space of solutions to a differential equation. In dimension 2, the symplectic reduction of is analyzed and the construction presented here is compared with that introduced in Donaldson (Fields Medallists’ Lectures, 1997) and Fujiki (Sugaku Expositions 5(2):173–191, 1992). Finally, conformally flat metrics and, for n = 6, K?hler metrics of constant holomorphic sectional curvature are shown to be contained in .      

Packing directed circuits

We prove a conjecture of Younger, that for every integern0 there exists an integert0 such that for every digraphG, eitherG hasn vertex-disjoint directed circuits, orG can be made acyclic by deleting at mostt vertices.Research partially supported by DONET ECHM contract CHRXCT930090.Research partially supported by DIMACS, by NSF grant DMS-9401981 and by ONR grant N00014-92-J-1965, and partially performed under a consulting agreement with Bellcore.Research partially supported by DIMACS, by Université de Paris VI, by NSF grant DMS-9303761 and by ONR grant N00014-93-1-0325, and partially performed under a consulting agreement with Bellcore.     

Un théorème sur les séries de Dirichlet

We considerk Dirichlet series a _j (n)n ^–s (1jk),k2. We suppose that for eachj the series a _j (n)n ^–s converges fors=s _j =j+it _j , and that Max j<1/(k–1). We prove that the (Dirichlet) product of these series converges uniformly on every bounded segment of the line es = (₁+...+ _k )/k+1–1/k and we estimate the rate of convergence. The number 1–1/k cannot be replaced by a smaller one.     

Reflection subgroups of reflection groups

Let G be a discrete group generated by reflections in hyperbolic or Euclidean space, and let H G be a finite index reflection subgroup. Suppose that the fundamental chamber of G is a finite volume polytope with k facets. We prove that the fundamental chamber of H has at least k facets.Translated from Funktsionalnyi Analiz i Ego Prilozheniya, Vol. 38, No. 4, pp. 90–92, 2004Original Russian Text Copyright © by A. A. Felikson and P. V. Tumarkin     

Effect of loading history on changes in the characteristic Angles and the length of the retardation trace

The local strains theory and the theory of small elastoplastic strains are used to determine the values of the components of the plastic strain vector {₁, ₂} for nonlinearity n=3 in five-dimensional Euclidean space in the case of complex loading along a two-segment broken line, when both tensile and compressive stresses are present in each loading stage. The relation between the vectors , and S and the tangents to the deformation and loading trajectories are examined. Values of the retardation trace are obtained in terms of the loading history. Numerical results have been derived with the aid of a BÉSM-3M computer.Institute of Polymer Mechanics, Academy of Sciences of the Latvian SSR, Riga. Translated from Mekhanika Polimerov, No. 1, pp. 92–97, January–February, 1971.     

Abschätzungen für\sum\limits_{n \leqslant N} {B_1 (n\alpha )}

Estimates for . Let and letB ₁(x)={x}–1/2. In this paper we shall give best possible estimates for . On the importance of this sum see the papers ofBehnke [2],Hardy andLittlewood [5],Hecke [6] andOstrowski [9].

---

---

Meinem verehrten Lehrer, Herrn Professor E. Hlawka zum siebzigsten Geburtstag gewidmet     

Modular intersection graphs

A graphG = (V, E) is a modular intersection graph on a finite setU if there is a family of subsetsS = {S _xx V} ofU and positive integerst < m such thatxy is an edge ofG if and only if |S _x S_y| (modm) t. Modular representations of various classes of graphs and studied as well as some related parameters.Research supported by Grant N00014-89-J-1643 from the Office of Naval Research.     

On some estimates based on sample behavior near high level excursions

Summary Let { _j } be a stationary sequence of weakly dependent random variables and letM _n ^(k) be thek-th largest value of _j , 1jn. The estimation of the parameters of the asymptotic distribution ofM _n ^(k) is considered using a procedure motivated by a limit theorem pertaining to the point process . A number of statistical issues concerning the procedure, including how to select the tuning parameters, are addressed. The second problem that we consider is the estimation of the filter of a moving average process with heavy tails. In particular, the investigation covers the moving average stable process. Motivated by ideas in Rootzén (1978), our estimator uses information contained in the sample behavior of the process near the largest excursion.Research supported by AFOSR Contract No. 91-0030, NAVY-ONR Grant No. N00014-92-J-1007, and NSF Grant No. 9107507     

The diffusive phase of a model of self-interacting walks

Summary We consider simple random walk onZ ^d perturbed by a factor exp[T ^–P J _T], whereT is the length of the walk and . Forp=1 and dimensionsd2, we prove that this walk behaves diffusively for all – < <₀, with ₀ > 0. Ford>2 the diffusion constant is equal to 1, but ford=2 it is renormalized. Ford=1 andp=3/2, we prove diffusion for all real (positive or negative). Ford>2 the scaling limit is Brownian motion, but ford2 it is the Edwards model (with the wrong sign of the coupling when >0) which governs the limiting behaviour; the latter arises since for ,T ^–p J _T is the discrete self-intersection local time. This establishes existence of a diffusive phase for this model. Existence of a collapsed phase for a very closely related model has been proven in work of Bolthausen and Schmock.     

The minimum area of a surface with prescribed boundary contour in a pseudoeuclidean space

LetE ^{n, k} be a pseudoeuclidean space with linear elementdx ₁ ² ++dx _n–k ² –dx _n–k ^+1/2 ––dx _n ² . The area of a smooth two-dimensional surface inE ^{n, k} is defined by , whereE, F, andG are the coefficients of the first fundamental form of the surface andD is the region of variation of the parametersu andv. The following theorem is proved: LetL be a piecewise smooth closed curve inE ^{n, k} (1kn–1). Then there exists a two-dimensional piecewise smooth surface of arbitrarily small area bounded by the curveL. 3 figures.Translated from Ukrainskií Geometricheskií Sbornik, No. 30, 1987, pp. 18–22.     

Tangential chow forms — rank 1 hypersurfaces in a Grassmannian

Let X ⁿ P ^N be an n-dimensional projective variety, and N–n–1kN–1. The closure in the Grassmannian G(k+1, N+1) of the set of k-planes meeting the smooth locus of X nontransversally is a tangential Chow form (TCF) of X.TCF's are generally hypersurfaces. We show that a hypersurface is a TCF iff its conormal form has rank 1, and that a TCF is a hypersurface iff some quadric in the second fundamental form of X has rank n+k+1–N.     

Classes of graphs that exclude a tree and a clique and are not vertex ramsey

A class of graphs is vertex Ramsey if for allH there existsG such that for all partitions of the vertices ofG into two parts, one of the parts contains an induced copy ofH. Forb (T,K) is the class of graphs that induce neitherT norK. LetT(k, r) be the tree with radiusr such that each nonleaf is adjacent tok vertices farther from the root than itself. Gyárfás conjectured that for all treesT and cliquesK, there exists an integerb such that for allG in Forb(T,K), the chromatic number ofG is at mostb. Gyárfás' conjecture implies a weaker conjecture of Sauer that for all treesT and cliquesK, Forb(T,K) is not vertex Ramsey. We use techniques developed for attacking Gyárfás' conjecture to prove that for allq, r and sufficiently largek, Forb(T(k,r),K _q ) is not vertex Ramsey.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

L 2-approximation by the translates of a function and related attenuation factors

Summary Let be thek-dimensional subspace spanned by the translates (·–2j/k),j=0, 1, ...,k–1, of a continuous, piecewise smooth, complexvalued, 2-periodic function . For a given functionfL ²(–, ), its least squares approximantS _kf from can be expressed in terms of an orthonormal basis. Iff is continuous,S _kf can be computed via its discrete analogue by fast Fourier transform. The discrete least squares approximant is used to approximate Fourier coefficients, and this complements the works of Gautschi on attenuation factors. Examples of include the space of trigonometric polynomials where is the de la Valleé Poussin kernel, algebraic polynomial splines where is the periodic B-spline, and trigonometric polynomial splines where is the trigonometric B-spline.     

General Blowings-up of ℙ2 and Injectivity of Gauss Maps

We consider the blowing-up Y _k of the projective plane along k general points P ₁,...,P _k . Let _k : Y _k ² be the projection map and E _i the exceptional divisor corresponding to P _i for 1ik. For m2 and km(m+3)/2–4 let _k be the invertible sheaf _k ^*( ²(m)) _{Y k} (–E ₁–···–E _k ) on Y _k , and let _k: Y _k ^N be the morphism corresponding to _k . As _k is a local embedding, the Gauss map _k corresponding to _k is defined on Y _k by _k (x)=(d _{x k} )(T _x (Y _k )) for all xY _k . We prove that this Gauss map _k is injective.     

Round-off error analysis of iterations for large linear systems

Summary We deal with the rounding error analysis of successive approximation iterations for the solution of large linear systemsA _x =b. We prove that Jacobi, Richardson, Gauss-Seidel and SOR iterations arenumerically stable wheneverA=A ^*>0 andA has PropertyA. This means that the computed resultx _k approximates the exact solution with relative error of order A·A ^–1 where is the relative computer precision. However with the exception of Gauss-Seidel iteration the residual vector Ax _k –b is of order A² A ^–1 and hence the remaining three iterations arenot well-behaved.This work was partly done during the author's visit at Carnegie-Mellon University and it was supported in part by the Office of Naval Research under Contract N00014-76-C-0370; NR 044-422 and by the National Science Foundation under Grant MCS75-222-55     

Powers of Sign Portraits of Real Matrices

The sign portrait S of a real n× n matrix is a matrix over the semiring with elements 0, 1, -1, and , where symbolizes indeterminateness. It is proved that if k is the least positive integer such that all the entries of S ^k are equal to , then k 2n ² – 3n + 2, and this bound is sharp. Bibliography: 6 titles.