Dual coordinate step methods for linear network flow problems

We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion of-complementary slackness, and most do not explicitly manipulate any global objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of newserial computational complexity results. We develop the basic theory of these methods and present two specific methods, the-relaxation algorithm for the minimum-cost flow problem, and theauction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N ³ logNC) and O(NA logNC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement-relaxation in a completely asynchronous, chaotic environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.Supported by Grant NSF-ECS-8217668 and by the Army Research Office under grant DAAL03-86-K-0171. Thanks are due to David Castañon, Paul Tseng, and Jim Orlin for their helpful comments.     

Intersection queries in sets of disks

In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report allk disks intersecting a query line segment in timeO(n ⁺ +k), wheren is the number of disks,=log₂(1+5)–1 0.695, and is an arbitrarily small positive constant. If the segment is a full line, the query time becomesO(n +k). For intersecting disks we obtain anO(n logn) size data structure that can answer an intersection query in timeO(n ^2/3 log² n+k). We also present a linear size data structure for ray shooting queries, whose query time isO(n ).The research of the first two authors was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The work of the third author was supported byDimacs (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center — NSF-STC88-09648.     

Large deviations for independent random walks

Summary We consider a system of independent random walks on . Let _n (x) be the number of particles atx at timen, and letL _n (x)=₀(x)+ ... + _n (x) be the total occupation time ofx by timen. In this paper we study the large deviations ofL _n (0)–L _n (1). The behavior we find is much different from that ofL _n (0). We investigate the limiting behavior when the initial configurations has asymptotic density 1 and when ₀(x) are i.i.d Poisson mean 1, finding that the asymptotics are different in these two cases.This work was done while the first author was on sabbatical at Cornell University. Both authors were partially supported by the National Science Foundation and the Army Research Office through the Mathematical Sciences Institute at Cornell     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.     

Global solutions describing the collapse of a spherical or cylindrical cavity

The collapse of a spherical (cylindrical) cavity in air is studied analytically. The global solution for the entire domain between the sound front, separating the undisturbed and the disturbed gas, and the vacuum front is constructed in the form of infinite series in time with coefficients depending on an appropriate similarity variable. At timet=0⁺, the exact planar solution for a uniformly moving cavity is assumed to hold. The global analytic solution of this initial boundary value problem is found until the collapse time (=(–1)/2) for 1+(2/(1+v)), wherev=1 for cylindrical geometry, andv=2 for spherical geometry. For higher values of , the solution series diverge at timet — 2(–1)/ (v(1+)+(1–)2) where =2/(–1). A close agreement is found in the prediction of qualitative features of analytic solution and numerical results of Thomaset al. [1].     

Increase of stable processes

One says thatt>0 is an increase time for a real-valued path if stays above the level (t) immediately after timet, and below (t) immediately before timet. Dvoretzkyet al.,⁽¹⁰⁾ proved that Brownian motion has no increase times a.s. This result is extended here to (strictly) stable processes. Specifically, the probability that a stable processX possesses increase times is 0 if and only ifP(X ₁0)1/2.     

On the character of convergence to Brownian local time. I

Summary Many results are known about the convergence of some processes to Brownian local time. Among such processes are the process of occupation times of Brownian motion, the number of downcrossings of Brownian motion over smaller and smaller intervals before timet, the number of visits of the recurrent integer-valued random walk to some point duringn steps and others. In this paper we consider the asymptotic behaviour of the differences between Brownian local time and some of the processes which converge to it.     

The Feynman-Kac formula with a Lebesgue-Stieltjes measure: An integral equation in the general case

Let u(t) be the operator associated by path integration with the Feynman-Kac functional in which the time integration is performed with respect to an arbitrary Borel measure instead of ordinary Lebesgue measurel. We show that u(t), considered as a function of time t, satisfies a Volterra-Stieltjes integral equation, denoted by (*). We refer to this result as the Feynman-Kac formula with a Lebesgue-Stieltjes measure. Indeed, when n=l, we recover the classical Feynman-Kac formula since (*) then yields the heat (resp., Schrödinger) equation in the diffusion (resp., quantum mechanical) case. We stress that the measure is in general the sum of an absolutely continuous, a singular continuous and a (countably supported) discrete part. We also study various properties of (*) and of its solution. These results extend and use previous work of the author dealing with measures having finitely supported discrete part (Stud. Appl. Math.76 (1987), 93–132); they seem to be new in the diffusion (or imaginary time) as well as in the quantum mechanical (or real time) case.Research partially supported by the National Science Foundation under Grant DMS 8703138. This work was also supported in part by NSF Grant 8120790 at the Mathematical Sciences Research Institute in Berkeley, U.S.A., the CNPq and the Organization of Latin American States at theInstituto de Matemática Pura E Aplicada (IMPA) in Rio de Janeiro, Brazil, as well as theUniversité Pierre et Marie Curie (Paris VI) and the Université Paris Dauphine in Paris, France.     

Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.     

Asymptotic Expansions for the Congestion Period for the M/M/∞ Queue

We consider the M/M/ queue with arrival rate , service rate and traffic intensity =/. We analyze the first passage distribution of the time the number of customers N(t) reaches the level c, starting from N(0)=m>c. If m=c+1 we refer to this time period as the congestion period above the level c. We give detailed asymptotic expansions for the distribution of this first passage time for , various ranges of m and c, and several different time scales. Numerical studies back up the asymptotic results.     

Scheduling jobs on heterogeneous processors

We consider the problem of schedulingn jobs nonpreemptively onm processors to minimize various weighted cost functions of job completion times. The time it takes processorj to process a job is distributed exponentially with rate parameter _j , independent of the other processors. Associated with jobi is a weightw _i . There are no precedence constraints and any job may be processed on any processor. Assume that _{1 2}...µ _m andw ₁w ₂...w _n . Then for certain weighted cost functions, the optimal policy is such that the processors can be partitioned into setsS ₁, ...,S _n+1 such that if the fastest available processor is in setS _i ,i=1, ...,n, then jobi should be assigned to it, and if it isS _n+1, it will never be used. After each assignment the jobs are renumbered (so that jobi+1 becomes jobi if jobi is assigned to a processor). The partitioning is independent of the job weights and the states (busy or idle) of the processors. The optimal policy can be determined in at most max {m, n} steps. If all the weights are identical, the optimal policy reduces to a simple threshold rule such that a job should be assigned to the fastest available processor, sayj, if there are more thanK _j jobs waiting.K _j will depend on ₁, ..., _j but not on _j+1, ...,µ _m . The optimal policy is also individually optimal in the sense that it minimizes the cost for each jobi subject to the constraint that processors will first be offered to the jobs in the order 1, 2, ...,n.We explicitly characterize the optimal policy for several specific examples of cost functions, such as weighted flow time, weighted discounted flowtime, and weighted number of tardy jobs.     

First passage percolation: The stationary case

Summary If the passage time of the edges of the ^d lattice are stationary, ergodic and have finite moment of orderp>d, then a.s. the set of vertices that can be reached within timet, has an asymptotic shape ast.     

Future independent times and Markov chains

Summary A random timeT is a future independent time for a Markov chain (X _n ) ₀ ifT is independent of (X _T+n ) _n ^/ =0 and if (X _T+n ) _n ^/ =0 is a Markov chain with initial distribution and the same transition probabilities as (X _n ) ₀ . This concept is used (with the conditional stationary measure) to give a new and short proof of the basic limit theorem of Markov chains, improving somewhat the result in the null-recurrent case.This work was supported by the Swedish Natural Science Research Council and done while the author was visiting the Department of Statistics, Stanford University     

Systèmes de sortie ℱ Dt prévisibles

Summary Given a random closed setM, adapted to a filtration ( _t ), we construct a local time ofM which is both ( _t ) adapted and ( _Dt ) predictable, whereD _t =inf{s>t: sM}. Similarly an exit system, both ( _t ) optional and ( _Dt ) predictable, is associated withM and with the process representing the future at each timet. The paper is motivated by the markovian case, where the general results are applied to Ray processes.     

On the occupation times of cones by Brownian motion

Summary We study some features concerning the occupation timeA _t of a d-dimensional coneC by Brownian motion. In particular, in the case whereC is convex, we investigate the asymptotic behaviour ofP(A₁u0, when the Brownian motion starts at the vertex ofC. We also give the precise integral test, which decides whether a.s., lim inf _t A _t/(tf(t))=0 or for a decreasing functionf.     

Priority queues with semi-exhaustive service

This paper studies a new type of multi-class priority queues with semi-exhaustive service and server vacations, which operates as follows: A single server continues serving messages in queuen until the number of messages decreases toone less than that found upon the server's last arrival at queuen, where 1nN. In succession, messages of the highest class present in the system, if any, will be served according to this semi-exhaustive service. Applying the delay cycle analysis and introducing a super-message composed of messages served in a busy period, we derive explicitly the Laplace-Stieltjes transforms (LSTs) and the first two moments of the message waiting time distributions for each class in the M/G/1-type priority queues with multiple and single vacations. We also derive a conversion relationship between the LSTs for waiting times in the multiple and single vacation models.     

Shock fluctuations in asymmetric simple exclusion

Summary The one dimensional nearest neighbors asymmetric simple exclusion process in used as a microscopic approximation to the Burgers equation. We study the process with rates of jumpsp>q to the right and left, respectively, and with initial product measure with densities < to the left and right of the origin, respectively (with shock initial conditions). We prove that a second class particle added to the system at the origin at time zero identifies microscopically the shock for all later times. If this particle is added at another site, then it describes the behavior of a characteristic of the Burgers equation. For vanishing left density (=0) we prove, in the scale t^1/2, that the position of the shock at timet depends only on the initial configuration in a region depending ont. The proofs are based on laws of large numbers for the second class particle.     

Maximum Monoreflections and Essential Extensions

An extension operator c in a category is an assignment, to each object A a monomorphism c _A : AcA. Seeking to approximate such a c by a functor, in our earlier paper Maximum monoreflections, we showed that with some hypotheses on the category, and on c, there is a monoreflection (c) maximum beneath c. Thus, in a suitable category of rings, using the complete ring of quotients operator Q, each object A has a maximum functorial ring of quotients (Q)A. But the proof gave no hint of how to calculate the general (c)A's, nor the particular (Q)A's. In the present paper, we give an explicit formula (and separate proof of existence) for the (c)A's, under more complicated hypotheses on the category and assuming the c _A 's are essential monomorphisms. We discuss briefly how the formula proves adequate to calculate the (Q)A's in Archimedean f-rings, and some related and necessary constructs in Archimedean l-groups.     

Black holes on the plane drawn by a Wiener process

Summary We say that the discD()R ², of radius , located around the origin isp-covered in timeT by a Wiener processW(·) if for anyzD() there exists a 0tT such thatW(t) is a point of the disc of radiusp, located aroundz. The supremum of those 's (0) is studied for which,D() isp-covered inT.     

On the dynamics of fine structure

Summary We investigate models for the dynamical behavior of mechanical systems that dissipate energy as timet increases. We focus on models whose underlying potential energy functions do not attain a minimum, possessing minimizing sequences with finer and finer structure that converge weakly to nonminimizing states. In Model 1 the evolution is governed by a nonlinear partial differential equation closely related to that of one-dimensional viscoelasticity, the underlying static problem being of mixed type. In Model 2 the equation of motion is an integro—partial differential equation obtained from that in Model 1 by an averaging of the nonlinear term; the corresponding potential energy is nonlocal.After establishing global existence and uniqueness results, we consider the longtime behavior of the systems. We find that the two systems differ dramatically. In Model 1, for no solution does the energy tend to its global minimum ast . In Model 2, however, a large, dense set of solutions realize global minimizing sequences; in this case we are able to characterize, asymptotically, how energy escapes to infinity in wavenumber space in a manner that depends upon the smoothness of initial data. We also briefly discuss a third model that shares the stationary solutions of the second but is a gradient dynamical system.The models were designed to provide insight into the dynamical development of finer and finer microstructure that is observed in certain material phase transformations. They are also of interest as examples of strongly dissipative, infinite-dimensional dynamical systems with infinitely many unstable modes, the asymptotic fate of solutions exhibiting in the case of Model 2 an extreme sensitivity with respect to the initial data.