A probably fast,provably optimal algorithm for rectilinear Steiner trees

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ? > 0, there exists b > 0 such that Prob[T(n) > 2^{b√n log n]>1–?, for n log n} > 1 – ?, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.     

Comparison of formulations and a heuristic for packing Steiner trees in a graph

In this paper, we consider the problem of packing Steiner trees in a graph. This problem arises during the global routing phase of circuit layout design. We consider various integer programming formulations and rank them according to lower bounds they provide as LP-relaxations. We discuss a solution procedure to obtain both lower and upper bounds using one of the LP-relaxations. Computational results to test the effectiveness of our procedures are provided.     

A short proof of a result of Pollak on Steiner minimal trees

The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least $\text{3}\text{2}$. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. However, the proof for n = 4 by Pollak is sufficiently complicated that no generalization to any other value of n has been found. We use a different approach to give a very short proof for the n = 4 case. This approach also allows us to attack the n = 5 case, though the proof is no longer short (to be reported in a subsequent paper).     

An upper bound on the number of Steiner triple systems

Richard Wilson conjectured in 1974 the following asymptotic formula for the number of n ‐vertex Steiner triple systems: \begin{align*} STS(n) = \left( (1+o(1))\frac{n}{e^2} \right)^{\frac{n^2}{6}}\end{align*}. Our main result is that The proof is based on the entropy method. As a prelude to this proof we consider the number F(n) of 1 ‐factorizations of the complete graph on n vertices. Using the Kahn‐Lovász theorem it can be shown that We show how to derive this bound using the entropy method. Both bounds are conjectured to be sharp. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 399–406, 2013     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

A note on the integrality gap of an ILP formulation for the periodic maintenance problem

We address the integrality gap of the integer linear program introduced by Grigoriev et al. (2006) [3] for the periodic maintenance problem. We prove that the integrality gap of this program is bounded by a constant.     

Analysis of Steiner subtrees of random trees for traceroute algorithms

We consider in this article the problem of discovering, via a traceroute algorithm, the topology of a network, whose graph is spanned by an infinite branching process. A subset of nodes is selected according to some criterion. As a measure of efficiency of the algorithm, the Steiner distance of the selected nodes, i.e. the size of the spanning subtree of these nodes, is investigated. For the selection of nodes, two criteria are considered: a node is randomly selected with a probability, which is either independent of the depth of the node (uniform model) or else in the depth biased model, is exponentially decaying with respect to its depth. The limiting behavior the size of the discovered subtree is investigated for both models. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

The Steiner tree problem I: Formulations,compositions and extension of facets

In this paper we give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP-relaxation of the undirected one.Corresponding author.     

A new existence proof for large sets of disjoint Steiner triple systems

A Steiner triple system of order v (briefly STS(v)) consists of a v-element set X and a collection of 3-element subsets of X, called blocks, such that every pair of distinct points in X is contained in a unique block. A large set of disjoint STS(v) (briefly LSTS(v)) is a partition of all 3-subsets (triples) of X into v-2 STS(v). In 1983–1984, Lu Jiaxi first proved that there exists an LSTS(v) for any v≡1 or with six possible exceptions and a definite exception v=7. In 1989, Teirlinck solved the existence of LSTS(v) for the remaining six orders. Since their proof is very complicated, it is much desired to find a simple proof. For this purpose, we give a new proof which is mainly based on the 3-wise balanced designs and partitionable candelabra systems.     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Minimizing the sum of weighted completion times in a concurrent open shop

We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if P≠NP, or strictly less than 4/3 if the Unique Games Conjecture also holds.     

A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem

In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+. The GOSST problem has some important applications. In network design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements.     

Vertex-Disjoint Packing of Two Steiner Trees: polyhedra and branch-and-cut

Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided. Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals in a few minutes. Received: August 1999 / Accepted: January 2001?Published online April 12, 2001     

A short proof of a theorem of Birkhoff

This paper gives a new proof of a theorem of G. Birkhoff: Every group can be represented as the automorphism group of a distributive lattice D; if is finite, D can be chosen to be finite. The new proof is short, and it is easily visualized. Received November 3, 1995; accepted in final form October 3, 1996.     

A lower bound on the number of Semi‐Boolean quadruple systems

A Steiner quadruple system of order 2ⁿ is Semi‐Boolean (SBQS(2ⁿ) in short) if all its derived triple systems are isomorphic to the point‐line design associated with the projective geometry PG(n?1, 2). We prove by means of explicit constructions that for any n, up to isomorphism, there exist at least 2^{? 3(n?4)/2?} regular and resolvable SBQS(2ⁿ). © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 229–239, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10050     

A short proof of the twelve-point theorem

We present a short elementary proof of the following twelve-point theorem. Let M be a convex polygon with vertices at lattice points, containing a single lattice point in its interior. Denote by m (respectively, m*) the number of lattice points in the boundary of M (respectively, in the boundary of the dual polygon). Then m + m* = 12.Translated from Matematicheskie Zametki, vol. 77, no. 1, 2005, pp. 117–120.Original Russian Text Copyright © 2005 by D. Repov, M. Skopenkov, M. Cencelj.This revised version was published online in April 2005 with a corrected issue number.     

A short proof for the nonvanishing of a character sum

Let χ be an odd residue class character with conductor f (a prime power) and order 2^h. It is shown that the nonvanishing of the sum χ(1) + 2χ(2) + … + fχ(f) follows directly from properties of the minimum polynomial of a 2^hth root of unity.