Graph bisection algorithms with good average case behavior

In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n ^{1?1/[(d+1)/2]}), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n ^2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:

1. the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,
2. whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),
3. the algorithm works well both theoretically and experimentally,
4. the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and
5. the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).

     

A subjective Bayesian approach to the theory of queues II — Inference and information in M/M/1 queues

This is a sequel to Part I of A Subjective Bayesian Approach to the Theory of Queues. The focus here is on inference and a use of Shannon's measure of information for assessing the amount of information conveyed by the various types of data from queues. The notation and terminology used here is established in Part I.     

Some inequalities for partial orders

We establish some inequalities connecting natural parameters of a partial order P. For example, if every interval [a,b] contains at most maximal chains, if some antichain has cardinality v, and if there are ₁ chains whose union is cofinal and coinitial in P, then the chain decomposition number for P is ₁v (Theorem 2.2), and the inequality is sharp in a certain sense (Section 3).This paper was written while the authors were visitors at the Laboratoire d'algèbre ordinale, Département de Mathématiques, Université Claude Bernard, Lyon 1, France.Research supported by NSERC grant # A5198.     

The Lax representation for an integrable class of relativistic dynamical systems

We exhibit the Lax pair for the class of relativistic dynamical systems recently introduced by Ruijsenaars and Schneider, whose equations of motion read, whereB is an arbitrary constant and the Weierstrass elliptic function.For the 3 academic years 1983–1986     

Summation of weakly dependent sequences by Cesàro methods

Пусть (X, A, u) — пространст во с конечной мерой, (ξ_k) ₁ ^∞ — последовательност ь функций, \(\xi _k \varepsilon L_{2r} (X), r > 1, \int\limits_X {\xi _k d\mu = 0} \) . Изучаются условия, п ри которых справедли вgа - у. з. б.ч., т. e. (ξ _k) суммируется к ну лю почти всюду методо м (С, а),а > 0. Приведем два резу льтата. 1) Если (ξ _k) — слабо мульт ипликативная систем а (в частности, мартингал-разности или независимая сист ема), то условие $$\mathop \sum \limits_1^\infty \mathop {\smallint }\limits_X \left| {\xi _k } \right|^{2r} d\mu \cdot c_r (k,\alpha )< \infty $$ влечетβ - у.з.б.ч. Здесьc _r(k,α)=k ^-2rα при 0<α<(r+1)/2r, c_r=k^?(r+1) In3r-1 k приа=(r+1)/2r, с_r=k^?(r+1) при а >(r+1)/2r. 2) Если (ξ _k) независимы,Mξ _k=0, (r+1)/2r<α=1, то условия $$\mathop \sum \limits_{k = 1}^\infty \frac{{(M\xi _k^2 )^r }}{{k^{r + 1} }}< \infty ,\mathop \sum \limits_{k = 1}^\infty \frac{{M|\xi _k |^{2r} }}{{k^{2r\alpha } }}< \infty $$ влекут за собой а - у. з. б. ч.     

Discrimination of converging hypotheses for a branching process

For a discrete-time homogeneous branching process starting with m particles, we consider the problem of discrimination of converging hypotheses for m using a statistic which is equal to the total number of particles in the process during its entire evolution.Translated from Statisticheskie Metody, pp. 63–69, 1982.     

Semiclassical Topological Flat Laguerre Planes Obtained by Pasting Along A Circle

A new rather large family of locally compact 2-dimensional topological Laguerre planes is introduced here. This family consists exactly of those Laguerre planes which can be obtained by pasting together two halves of the classical real Laguerre plane along a circle suitably. Isomorphism classes and automorphism groups of these planes are determined. Together with [9] this gives a complete classification of all semicalssical topological flat Lguerre planes.     

Temperature dependence of development of slip bands and of strain hardening in AgCl crystals

The dependence of the flow stress and the slip band density on the plastic strain has been measured at 201 K, 293 K and 363 K. The growth of deformation concentrated in an average slip band has been stated. The types of obstacles acting against the rise and development of a slip band and the temperature dependence of the strain hardening in AgCl crystals are discussed. An equation stating the dependence of the flow stress on the slip band density is presented. The hardening in AgCl crystals is classified as the stage III — hardening.     

An introduction to covariant superstring field theories

A pedagogical account is given of the recent developments in covariant (super)string field theories. After reviewing the construction of the free open bosonic string field theory, the super-symmetric case is treated and the space-time supersymmetry transformations are explained. The present status and some future problems are also summarized.Invited talk presented at the International Conference Selected Topics in Quantum Field Theory and Mathematical Physics, Bechyn, Czechoslovakia, June 23–27, 1986.On leave of absence fromNational Laboratory for High Energy Physics (KEK), Tsukuba, Ibaraki, Japan.I would like to thank A. Neveu, H. Nicolai and P. West for many discussions, and the CERN Theoretical Physics Division for hospitality and generous support.     

Splitting the Cartesian point

It is argued that the point structure of space and time must be constructed from the primitive extensional character of space and time. A procedure for doing this is laid down and applied to one-dimensional and two-dimensional systems of abstract extensions. Topological and metrical properties of the constructed point systems, which differ nontrivially from the usual and ² models, are examined. Briefly, constructed points are associated with directions and the Cartesian point is split. In one-dimension each point splits into a point pair compatible with the linear ordering. An application to one-dimensional particle motion is given, with the result that natural topological assumptions force the number of left point, right point transitions to remain locally finite in a continuous motion. In general, Cartesian points are seen to correspond to certain filters on a suitable Boolean algebra. Constructed points correspond to ultrafilters. Thus, point construction gives a natural refinement of the Cartesian systems.