Quasi‐Periodic Almost‐Collision Orbits in the Spatial Three‐Body Problem

In a system of particles, quasi‐periodic almost‐collision orbits are collisionless orbits along which two bodies become arbitrarily close to each other—the lower limit of their distance is zero but the upper limit is strictly positive—and are quasi‐periodic in a regularized system up to a change of time. Their existence was shown in the restricted planar circular three‐body problem by A.~Chenciner and J. Llibre, and in the planar three‐body problem by J. Féjoz. In the spatial three‐body problem, the existence of a set of positive measure of such orbits was predicted by C. Marchal. In this article, we present a proof of this fact.© 2015 Wiley Periodicals, Inc.     

Universal Classes of MV‐chains with Applications to Many‐valued Logics

In this paper we characterize, classify and axiomatize all universal classes of MV‐chains. Moreover, we accomplish analogous characterization, classification and axiomatization for congruence distributive quasivarieties of MV‐algebras. Finally, we apply those results to study some finitary extensions of the Łukasiewicz infinite valued propositional calculus.     

Solvable Cases of the No-Wait Flow-Shop Scheduling Problem

The no-wait flow-shop scheduling problem (NWFSSP) with a makespan objective function is considered. As is well known, this problem is ????-hard for three or more machines. Therefore, it is interesting to consider special cases, i.e. special structured processing time matrices, that allow polynomial time solution algorithms. Furthermore, it is well known that the NWFSSP with a makespan objective function can be formulated as a travelling salesman problem (TSP). It is observed that special structured processing time matrices for the NWFSSP lead to special structured distance matrices for which the TSP is polynomially solvable. Using this observation, it is shown that some NWFSSPs with fixed processing times on all except two machines are well solvable while the others are conjectured to be ????-hard. Also, it is shown that NWFSSPs with a mean completion time objective function restricted to semi-ordered processing time matrices are easily solvable.     

现代物流技术中装卸工问题的拟多项式时间可解情况

装卸工问题是从现代物流技术中提出的一个实际问题，这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过。现代物流业的迅速发展，促成和推动装卸工问题的提出和研究。装卸工问题是一个新的NP困难的组合优化问题，本文研究限制情形下的装卸工问题，并证明是拟多项式时间可解的。     

Well Solvable Cases of the Quadratic Assignment Problem with Monotone and Bimonotone Matrices

Conditions imposed on the matrices of the Quadratic Assignment Problem (QAP) are derived such that an optimum of the QAP is attained on a given permutation. These conditions describe four new sets of matrices, which, in the general case, are not anti-Monge and Toeplitz matrices that were used for most of the known well solvable special cases of the QAP.     

The Universally Solvable Embedding Problem with Cyclic Kernel of Order 8

It is proved that the universally solvable embedding problem with cyclic kernel of order 8 is semidirect. Bibliography: 4 titles.     

Explicitly Solvable Nonlocal Eigenvalue Problems and the Stability of Localized Stripes in Reaction‐Diffusion Systems

The transverse stability of localized stripe patterns for certain singularly perturbed two‐component reaction‐diffusion (RD) systems in the asymptotic limit of a large diffusivity ratio is analyzed. In this semi‐strong interaction regime, the cross‐sectional profile of the stripe is well‐approximated by a homoclinic pulse solution of the corresponding 1‐D problem. The linear instability of such homoclinic stripes to transverse perturbations is well known from numerical simulations to be a key mechanism for the creation of localized spot patterns. However, in general, owing to the difficulty in analyzing the associated nonlocal and nonself‐adjoint spectral problem governing stripe stability for these systems, it has not previously been possible to provide an explicit analytical characterization of these instabilities, including determining the growth rate and the most unstable mode within the band of unstable transverse wave numbers. Our focus is to show that such an explicit characterization of the transverse instability of a homoclinic stripe is possible for a subclass of RD system for which the analysis of the underlying spectral problem reduces to the study of a rather simple algebraic equation in the eigenvalue parameter. Although our simplified theory for stripe stability can be applied to a class of RD system, it is illustrated only for homoclinic stripe and ring solutions for a subclass of the Gierer–Meinhardt model and for a three‐component RD system modeling patterns of criminal activity in urban crime.     

On the Hamilton‐Waterloo Problem for Bipartite 2‐Factors

Given two 2‐regular graphs F₁ and F₂, both of order n, the Hamilton‐Waterloo Problem for F₁ and F₂ asks for a factorization of the complete graph into α₁ copies of F₁, α₂ copies of F₂, and a 1‐factor if n is even, for all nonnegative integers α₁ and α₂ satisfying . We settle the Hamilton‐Waterloo Problem for all bipartite 2‐regular graphs F₁ and F₂ where F₁ can be obtained from F₂ by replacing each cycle with a bipartite 2‐regular graph of the same order.     

Dynamics in the Schwarzschild Isosceles Three Body Problem

The Schwarzschild potential, defined as \(U(r)=-A/r-B/r^3\) , where \(r\) is the relative distance between two mass points and \(A,B>0\) , models astrophysical and stellar dynamics systems in a classical context. In this paper we present a qualitative study of a three mass point system with mutual Schwarzschild interaction where the motion is restricted to isosceles configurations at all times. We retrieve the relative equilibria and provide the energy–momentum diagram. We further employ appropriate regularization transformations to analyze the behavior of the flow near triple collision. We emphasize the distinct features of the Schwarzschild model when compared to its Newtonian counterpart. We prove that, in contrast to the Newtonian case, on any level of energy the measure of the set on initial conditions leading to triple collision is positive. Further, whereas in the Newtonian problem triple collision is asymptotically reached only for zero angular momentum, in the Schwarzschild problem the triple collision is possible for nonzero total angular momenta (e.g., when two of the mass points spin infinitely many times around the center of mass). This phenomenon is known in celestial mechanics as the black-hole effect and is understood as an analog in the classical context of behavior near a Schwarzschild black hole. Also, while in the Newtonian problem all triple collision orbits are necessarily homothetic, in the Schwarzschild problem this is not necessarily true. In fact, in the Schwarzschild problem there exist triple collision orbits that are neither homothetic nor homographic.     

Lyons‐Pemantle‐Peres Monotonicity Problem for High Biases

The speed v(β) of a β‐biased random walk on a Galton‐Watson tree without leaves is increasing for β ≥ 1160. © 2014 Wiley Periodicals, Inc.     

Multiple Order Pick Sequencing in a Carousel System: A Solvable Case of the Rural Postman Problem

We consider the problem of sequencing picks in a set of orders on a single carousel. First we consider the situation in which the sequence of the orders is given. For this problem we present an efficient dynamic programming algorithm. Second, we consider the problem without a given order sequence. We simplify this problem to a Rural Postman Problem on a circle and solve this problem to optimality. Finally, we show that the solution of the Rural Postman Problem requires at most 1.5 revolutions more than a lower bound of an optimum solution to the original problem.     

Optimal Regularity for the No‐Sign Obstacle Problem

In this paper we prove the optimal $C^{1,1}(B_{1/2})$ ‐regularity for a general obstacle‐type problem under the assumption that $f*N$ is $C^{1,1}(B_1)$ , where N is the Newtonian potential. This is the weakest assumption for which one can hope to get $C^{1,1}$ ‐regularity. As a by‐product of the $C^{1,1}$ ‐regularity we are able to prove that, under a standard thickness assumption on the zero set close to a free boundary point $x^0$ , the free boundary is locally a $C^1$ ‐graph close to $x^0$ provided f is Dini. This completely settles the question of the optimal regularity of this problem, which has been the focus of much attention during the last two decades. © 2012 Wiley Periodicals, Inc.     

Variants of the Hajnal-Szemerédi Theorem

The Hajnal-Szemerédi Theorem [Hajnal & Szemerédi, Colloq Math Soc J Bolyai, 1970] states that a graph with hk vertices and minimum degree at least (h − 1)k contains k vertex disjoint copies of K_h. Its proof is not algorithmic. Here, we present an algorithm that, for a fixed h, finds in such a graph k − C(h) vertex disjoint copies of K_h in polynomial time in k, C(h) being a constant depending on h only. The proof suggests a variant of the theorem for h-partite graphs, which is conjectured here and proven in a slightly weaker form in some special cases. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 275–282, 1999     

Variants of the Two Machine Flow Shop Problem connected with factorization of matrix functions

In this paper we consider a number of variants of the Two Machine Flow Shop Problem. In these variants the makespan is given and the problem is to find a schedule that meets this makespan, thereby minimizing the infeasibilities of the jobs in a prescribed sense: In the max-variant the maximum infeasibility of the jobs is to be minimized, whereas in the sum-variant the objective is to minimize the sum of the infeasibilities of the jobs. For both variants observations about the structure of the optimal schedules are presented. In particular, it is proved that every instance of these problems has an optimal permutation schedule. It is also shown that the max-variant can be solved by Johnson's Rule. For the sum-variant this is not the case: For solving this problem to optimality something quite different is necessary. Both variants are connected with factorization problems for certain rational matrix functions. The factorizations involved are optimal in some sense and generalize the notion of complete factorization. In this way a connection is established between job scheduling theory on one hand, and mathematical systems theory on the other.     

The Degree‐Diameter Problem for Claw‐Free Graphs and Hypergraphs

We study the degree‐diameter problem for claw‐free graphs and 2‐regular hypergraphs. Let be the largest order of a claw‐free graph of maximum degree Δ and diameter D. We show that , where , for any D and any even . So for claw‐free graphs, the well‐known Moore bound can be strengthened considerably. We further show that for with (mod 4). We also give an upper bound on the order of ‐free graphs of given maximum degree and diameter for . We prove similar results for the hypergraph version of the degree‐diameter problem. The hypergraph Moore bound states that the order of a hypergraph of maximum degree Δ, rank k, and diameter D is at most . For 2‐regular hypergraph of rank and any diameter D, we improve this bound to , where . Our construction of claw‐free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank .     

The Hamilton–Waterloo Problem for ‐Factors and ‐Factors

The Hamilton–Waterloo problem asks for a 2‐factorization of (for v odd) or minus a 1‐factor (for v even) into ‐factors and ‐factors. We completely solve the Hamilton–Waterloo problem in the case of C₃‐factors and ‐factors for .     

A Multivalued Approach to the Planar Isosceles Three Body Problem

The isosceles three body problem consists of three point masses located on the vertices of an isosceles triangle on the plane. The two masses on the asymmetric edge are equal. This problem has been extensively studied but not as a perturbation of the Kepler problem. In this case we arrive at a differential inclusion as a natural formulation when we regularize the problem. We also derive an extension of the vectorfield that allows us to consider orbits across singular sets.