On H-Linked Graphs

For a fixed multigraph H, possibly containing loops, with V(H)={h₁, . . . , h_k}, we say a graph G is H-linked if for every choice of k vertices v₁, . . . , v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). This notion clearly generalizes the concept of k-linked graphs (as well as other properties). In this paper we determine, for a connected multigraph H and for any sufficiently large graph G, a sharp lower bound on δ(G) (depending upon H) such that G is H-linked.     

Iterative patching and the asymmetric traveling salesman problem

Although Branch-and-Bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the classical BnB trees, and that solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover, Gutin, Yeo and Zverovich (2001) and the Karp–Steele procedure are the fastest, and that ‘iterative’ Modified Karp–Steele patching generates the smallest search trees.     

Further advances on low-energy lunar impact dynamics

We extend the analysis, started in a previous work [1], concerning the formation of lunar impact craters due to low-energy trajectories. First, we adopt the Circular Restricted Three-Body Problem and consider different choices of initial conditions inside the stable invariant manifold associated with the central invariant one in the neighborhood of the L₂ equilibrium point in the Earth-Moon system. Then we move to the Bicircular Restricted Four-Body Problem to study the effect of the Sun on the distribution of impacts on the Moon’s surface.     

Parallel connections over symmetric spaces

Let M be a simply connected Riemannian symmetric space, with at most one flat direction. We show that every Riemannian (or unitary) vector bundle with parallel curvature over M is an associated vector bundle of a canonical principal bundle, with the connection inherited from the principal bundle. The problem of finding Riemannian (or unitary) vector bundles with parallel curvature then reduces to finding representations of the structure group of the canonical principal bundle.     

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.     

The M/M/c with critical jobs

We consider theM/M/c queue, where customers transfer to a critical state when their queueing (sojourn) time exceeds a random time. Lower and upper bounds for the distribution of the number of critical jobs are derived from two modifications of the original system. The two modified systems can be efficiently solved. Numerical calculations indicate the power of the approach.     

Balinski—Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and show that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski—Tucker (B—T) Simplex Tableaus. Furthermore, we give a strong polynomial algorithm for constructing such a B—T Simplex Tableau when a solution in the relative interior of the optimal face is known. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Chimie organométallique du niobium VIII. Etude détaillée de la réaction d'acétyléniques perfluorés avec (η5C5H5)2NbH3: Mise en evídence de la coupure de liaison C-F,de la formation de liaison Nb-F et de la reduction du niobium. Structure cristalline d'un dérivé niobiacyclopentadiène

Hexafluorobutyne (CF₃CCCF₃ = Hfb) reacts with Cp₂NbH₃ (Cp = η⁵-C₅H₅) affording five new complexes I–V, whose structures have been studied by mass,

Ir, ESR and NMR spectroscopy. The X-ray study of II shows the presence of a planar NbC₄ ring Nb—C(1): 2.25(5); C(1)—C(2): 1.31(7); C(2)—C(3): 1.53(8); C(3)—(4): 1.34(7); C(4)—Nb: 2.23(5) Å. With trifluoropropyne (CF₃CCH = tfp), only the analog of III, i.e. Cp₂NbFf(tfpH), has been isolated.