Fly Cheaply: On the Minimum Fuel Consumption Problem

In planning a flight, stops at intermediate airports are sometimes necessary to minimize fuel consumption, even if a direct flight is available. We investigate the problem of finding the cheapest path from one airport to another, given a set of n airports in ² and a function l: ² × ² → ⁺ representing the cost of a direct flight between any pair. Given a source airport s, the cheapest-path map is a subdivision of ² where two points lie in the same region iff their cheapest paths from s use the same sequence of intermediate airports. We show a quadratic lower bound on the combinatorial complexity of this map for a class of cost functions. Nevertheless, we are able to obtain subquadratic algorithms to find the cheapest path from s to all other airports for any well-behaved cost function l: our general algorithm runs in O(n^{4/3 +} ) time, and a simpler, more practical variant runs in O(n^{3/2 +} ) time, while a special class of cost functions requires just O(n log n) time.     

A Boundedness Criterion via Atoms for Linear Operators in Hardy Spaces

Let p∈(0,1] and s≥[n(1/p−1)], where [n(1/p−1)] denotes the maximal integer no more than n(1/p−1). In this paper, the authors prove that a linear operator T extends to a bounded linear operator from the Hardy space H ^p (ℝ ⁿ ) to some quasi-Banach space ℬ if and only if T maps all (p,2,s)-atoms into uniformly bounded elements of ℬ.      

Finding intersection of rectangles by range search

Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)^2k−1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)^2k) and the time for each query is O((log n)^2k−1 + s). For the third problem the total time is O(n log n + n(log n)^2(k−1) + s) for k ≥ 1.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Circuits including a given set of vertices

Let G = (V, E) be a digraph of order n, satisfying Woodall's condition ? x, y ∈ V, if (x, y) ? E, then d⁺(x) + d^?(y) ≥ n. Let S be a subset of V of cardinality s. Then there exists a circuit including S and of length at most Min(n, 2s). In the case of oriented graphs we obtain the same result under the weaker condition d⁺(x) + d^?(y) ≥ n – 2 (which implies hamiltonism).     

Resolvent Estimates for Operators Belonging to Exponential Classes

For a, α > 0 let E(a, α) be the set of all compact operators A on a separable Hilbert space such that s _n (A) = O(exp(-an^α)), where s _n (A) denotes the n-th singular number of A. We provide upper bounds for the norm of the resolvent (zI − A)⁻¹ of A in terms of a quantity describing the departure from normality of A and the distance of z to the spectrum of A. As a consequence we obtain upper bounds for the Hausdorff distance of the spectra of two operators in E(a, α).      

The structure of injective covers of special modules

In this paper, we prove that the injective cover of theR-moduleE(R/B)/R/B for a prime ideal B ofR is the direct sum of copies ofE(R/B) for prime ideals D ⊃ B, and if B is maximal, the injective cover is a finite sum of copies ofE(R/B). For a finitely generatedR-moduleM withn generators andG an injectiveR-module, we argue that the natural mapG ⁿ →G ⁿ/Hom _R (M, G) is an injective precover if Ext _R ¹ (M, R) = 0, and that the converse holds ifG is an injective cogenerator ofR. Consequently, for a maximal ideal R ofR, depth_R R ≧ 2 if and only if the natural mapE(R/R) →E(R/R)/R/R is an injective cover and depth_R R > 0.     

On holomorphic curves in a complex Grassmann manifold <Emphasis Type="Italic">G</Emphasis>(2, <Emphasis Type="Italic">n</Emphasis>)

Let s : S ² → G(2, n) be a linearly full totally unramified non-degenerate holomorphic curve in a complex Grassmann manifold G(2, n), and let K(s) be its Gaussian curvature. It is proved that K(s) = \frac4n-2{K(s) = \frac{4}{n-2}} if K(s) satisfies K(s) 3 \frac4n-2{K(s) \geq \frac{4}{n-2}} or K(s) ￡ \frac4n-2 {K(s) \leq \frac{4}{n-2} } everywhere on S ². In particular, K(s) = \frac4n-2{K(s) = \frac{4}{n-2}} if K(s) is constant.     

Cycles in a random graph near the critical point

Let G(n, M) be a graph chosen at random from the family of all labelled graphs with n vertices and M(n) = 0.5n + s(n) edges, where s³(n)n^?2→∞ but s(n) = o(n). We find the limit distribution of the length of shortest cycle contained in the largest component of G(n, M), as well as of the longest cycle outside it. We also describe the block structure of G(n, M) and derive from this result the limit probability that G(n, M) contains a cycle with a diagonal. Finally, we show that the probability tending to 1 as n-→∞ the length of the longest cycle in G(n, M) is of the order s²(n)/n.     

Relations between some constants associated with finite dimensional Banach spaces

We define the asymmetry constants(E) of a Banach spaceE, and show examples of finite-dimensional spaces with “large” asymmetry constants. IfE isn-dimensional,λ(E)17its projection constant and π ₁(I _E ) the absolutely summing norm of the identity operatorI _E , thenn≦λ(E)π₁(I _E )≤n(s(E))². Similar equations linking thep-absolutely summing and the nuclear norms ofI _E are established. We also obtain estimates on these norms, for example π₂(I _E )=√n. The contribution of this author is a part of a Ph.D. Thesis prepared at the Hebrew University of Jerusalem under the supervision of Professor J. Lindenstrauss whose guidance and valuable suggestions are gratefully acknowledged.     

A Baby Steps/Giant Steps Probabilistic Algorithm for Computing Roadmaps in Smooth Bounded Real Hypersurface

We consider the problem of constructing roadmaps of real algebraic sets. This problem was introduced by Canny to answer connectivity questions and solve motion planning problems. Given s polynomial equations with rational coefficients, of degree D in n variables, Canny’s algorithm has a Monte Carlo cost of sⁿlog(s)D^O(n2)s^{n}\log(s)D^{O(n^{2})} operations in ℚ; a deterministic version runs in time sⁿlog(s)D^O(n4)s^{n}\log(s)D^{O(n^{4})} . A subsequent improvement was due to Basu, Pollack, and Roy, with an algorithm of deterministic cost s^d+1D^O(n2)s^{d+1}D^{O(n^{2})} for the more general problem of computing roadmaps of a semi-algebraic set (d≤n is the dimension of an associated object).     

Values of the Euler Function in Various Sequences

Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)^r = λ(n)^s, where r ≥ s ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.     

The <Emphasis Type="Italic">s</Emphasis>-energy of spherical designs on <Emphasis Type="Italic">S</Emphasis><Superscript>2</Superscript>

This paper investigates the s-energy of (finite and infinite) well separated sequences of spherical designs on the unit sphere S ². A spherical n-design is a point set on S ² that gives rise to an equal weight cubature rule which is exact for all spherical polynomials of degree ≤n. The s-energy E _s (X) of a point set of m distinct points is the sum of the potential for all pairs of distinct points . A sequence Ξ = {X _m } of point sets X _m ⊂S ², where X _m has the cardinality card(X _m )=m, is well separated if for each pair of distinct points , where the constant λ is independent of m and X _m . For all s>0, we derive upper bounds in terms of orders of n and m(n) of the s-energy E _s (X _m(n)) for well separated sequences Ξ = {X _m(n)} of spherical n-designs X _m(n) with card(X _m(n))=m(n).      

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.     

Skew *-derivations with power-central values

Let R be a prime ring with involution * and d be a nonzero derivation on R such that d(x ^*) = -d(x)^* for all x ∈ R. Suppose that n ≥ 1 is a fixed integer. Then (I) if d(s) ⁿ = 0 for all s = s ^*, then R is either a commutative domain or an order in a 4-dimensional central simple algebra; (II) if d(s) ⁿ ∈Z, the center of R for all s = s ^*, then R is either a commutative domain or an order in a simple algebra of dimension 4 or 16 over its center.     

On the Range of Possible Integrities of Graphs G(n, k)

We discuss the range of values for the integrity of a graphs G(n, k) where G(n, k) denotes a simple graph with n vertices and k edges. Let I _max(n, k) and I _min(n, k) be the maximal and minimal value for the integrity of all possible G(n, k) graphs and let the difference be D(n, k) = I _max(n, k) − I _min(n, k). In this paper we give some exact values and several lower bounds of D(n, k) for various values of n and k. For some special values of n and for s < n ^1/4 we construct examples of graphs G _n  = G _n (n, n + s) with a maximal integrity of I(G _n ) = I(C _n ) + s where C _n is the cycle with n vertices. We show that for k = n ²/6 the value of D(n, n ²/6) is at least \frac?6-13n{\frac{\sqrt{6}-1}{3}n} for large n.     

Cutting hyperplane arrangements

We consider a collectionH ofn hyperplanes in E ^d (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all E ^d and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r ^d ) simplices (which is asymptotically optimal). Forr≤n ^1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn) ^O(1) r ^d−1). In the plane we achieve a time boundO(nr) forr≤n ^1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For ann point setX⊆E ^d and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}), In timeO(n(logn) ^O(1) r ^d−1 +r ^O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly. A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.     

Polynomial algorithms for a class of minimum rank-two cost path problems

In this paper, we develop two algorithms for finding a directed path of minimum rank-two monotonic cost between two specified nodes in a network with n nodes and m arcs. Under the condition that one of the vectors characterizing the cost function f is binary, one yields an optimal solution in O(n³) or O(nm log n) time if f is quasiconcave; the other solves any problem in O(nm + n ² log n) time.     

Efficiency of the polyphase merge and a related method

A sorting technique known as the polyphase merge is described. The notationE _n ^(p) is introduced for the effective power of the merge. It is defined for the maximal file that can be sorted withinn passes withp+1 available magnetic tape stations. Then the valueE ^(p)=lim _n E _n ^(p) is evaluated as a function ofp. UsingE ^(p) as a measure of efficiency the author discusses the polyphase merge comparing it with a merge technique which is essentially a combination of the polyphase and the balanced merge. To the author's knowledge this technique is new.     

Modified Cholesky algorithms: a catalog with new approaches

Given an n ×  n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A +  E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A +  E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of ||E||₂ =  O(n ²). An algorithm of Schnabel and Eskow further guarantees ||E||₂ =  O(n). We present variants that also ensure ||E||₂ =  O(n). Moré and Sorensen and Cheng and Higham used the block LBL ^T factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O(n ³) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL ^T -LBL ^T factorization, with T tridiagonal, that guarantees a modification cost of at most O(n ²). H.-r. Fang’s work was supported by National Science Foundation Grant CCF 0514213. D. P. O’Leary’s work was supported by National Science Foundation Grant CCF 0514213 and Department of Energy Grant DEFG0204ER25655.