Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound

Recently, Byrka, Grandoni, Rothvoß and Sanità gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm.     

Exponential approximation schemata for some network design problems

We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled.     

A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints

The paper deals with a problem motivated by survivability issues in multilayer IP-over-WDM telecommunication networks. Given a set of traffic demands for which we know a survivable routing in the IP layer, our purpose is to look for the corresponding survivable topology in the WDM layer. The problem amounts to Multiple Steiner TSPs with order constraints. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We also present new valid inequalities and discuss their facial aspect. Based on this, we devise a Branch-and-cut algorithm and present preliminary computational results.     

Random polarizations

We derive conditions under which random sequences of polarizations (two-point symmetrizations) on S^d${\mathbb{S}}^d$, R^d${\mathbb{R}}^d$, or H^d${\mathbb{H}}^d$ converge almost surely to the symmetric decreasing rearrangement. The parameters for the polarizations are independent random variables whose distributions need not be uniform. The proof of convergence hinges on an estimate for the expected distance from the limit that yields a bound on the rate of convergence. In the special case of i.i.d. sequences, almost sure convergence holds even for polarizations chosen at random from suitable small sets. As corollaries, we find bounds on the rate of convergence of Steiner symmetrizations that require no convexity assumptions, and show that full rotational symmetry can be achieved by randomly alternating Steiner symmetrizations in a finite number of directions that satisfy an explicit non-degeneracy condition. We also present some negative results on the rate of convergence and give examples where convergence fails.     

The hydrogen bond under pressure

The hydrogen bonds are quite pervasive in several classes of materials. Its parameters are known to show systematic variations with hydrogen bond length, and pressure variable is thus a natural way for studying hydrogen bonded substances. In this article, we review the unifying features as obtained through several experimental and theoretical investigations. Amongst other things, it is examined whether the observed pressure-induced variations in parameters of hydrogen bonds are consistent with the co-relations known on different chemical substances at normal pressure. In particular, the controversies on variations of O–H and H- - -O pairs with pressure and symmetrization of hydrogen bond have been resolved. The effects of close packing promoted by pressure such as formation of muli-centered hydrogen bonds and steric repulsions and the way the hydrogen bonds counter these in different ways are also examined.     

Engel conditions and symmetric tensors

In a recent study of Engel Lie rings, Serena Cicalò and Willem de Graaf have given a practical set of conditions for an additively finitely generated Lie ring L to satisfy an Engel condition. We present a simpler and more direct proof of this fact. Our main result generalizes this in the language of tensor algebra, and describes a relatively small generating set for the module generated by all n-th tensor powers of elements of a finitely generated ?-module M, in terms of a generating set for M.     

Exact approaches for solving robust prize-collecting Steiner tree problems

In the Prize-Collecting Steiner Tree Problem (PCStT) we are given a set of customers with potential revenues and a set of possible links connecting these customers with fixed installation costs. The goal is to decide which customers to connect into a tree structure so that the sum of the link costs plus the revenues of the customers that are left out is minimized. The problem, as well as some of its variants, is used to model a wide range of applications in telecommunications, gas distribution networks, protein–protein interaction networks, or image segmentation.     

On a question of Thas on partial 3‐(qn + 1, q + 1, 1) designs

In this note, we answer a question of JA Thas about partial $3$‐ $\left(q^n+1,q+1,1\right)$ designs. We then extend this answer to a result about the embedding of certain partial $3$‐ $\left(q^2+1,q+1,1\right)$ designs into Möbius planes.     

Large monochromatic components in 3‐edge‐colored Steiner triple systems

It is known that in any r‐coloring of the edges of a complete r‐uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on n vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3‐coloring of the edges? Gyárfás proved that $\left(2n+3\right)/3$ is an absolute lower bound and that this lower bound is best possible for infinitely many $n$. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually $\left(1?o\left(1\right)\right)n$. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest 3‐partite hole (ie, disjoint sets $X_1,X_2,X_3$ with $|X_1|=|X_2|=|X_3|$ such that no edge intersects all of $X_1,X_2,X_3$) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the structure of the Steiner triple system and the coloring of its edges are restricted in a certain way. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.