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.     

Symmetrization of matrix technique in a finite element context

A finite element Galerkin-based formulation of the mass conservation and momentum equations can require, if convective type terms are retained in the coefficient matrix, a non-symmetric solver. The resulting increase in core storage for efficient utilization of CPU time can be considerable. The current paper advocates a simple symmetrization of matrix technique, at element level which results in a considerable reduction in core requirement. The increase in CPU time required when solving linear systems of equations is considerable. However, for nonlinear systems the penalty can be negligible.     

Generalized Steiner Systems GS(2, 4, v, 2) with v a Prime Power ≡ 7 (mod 12)

Generalized Steiner systems GS(2, 4, v, g) were first introduced by Etzion and were used to construct optimal constant weight codes over an alphabet of size g + 1 with minimum Hamming distance 5, in which each codeword has length v and weight 4. Etzion conjectured that the necessary conditions v 1 (mod 3) and v ; 7 are also sufficient for the existence of a GS(2,4,v,2). Except for the example of a GS(2,4,10,2) and some recursive constructions given by Etzion, nothing else is known about this conjecture. In this paper, Weil's theorem on character sum estimates is used to show that the conjecture is true for any prime power v 7 (mod 12) except v = 7, for which there does not exist a GS(2,4,7,2).     

Tactical Decompositions of Steiner Systems and Orbits of Projective Groups

Block's lemma states that the numbers m of point-classes and n of block-classes in a tactical decomposition of a 2-(v, k, ) design with b blocks satisfy m n m + b – v. We present a strengthening of the upper bound for the case of Steiner systems (2-designs with = 1), together with results concerning the structure of the block-classes in both extreme cases. Applying the results to the Steiner systems of points and lines of projective space PG(N, q), we obtain a complete classification of the groups inducing decompositions satisfying the upper bound; answering the analog of a question raised by Cameron and Liebler (P.J. Cameron and R.A. Liebler, Lin. Alg. Appl. 46 (1982), 91–102) (and still open).     

Optimal doubly constant weight codes

A doubly constant weight code is a binary code of length n₁ + n₂, with constant weight w₁ + w₂, such that the weight of a codeword in the first n₁ coordinates is w₁. Such codes have applications in obtaining bounds on the sizes of constant weight codes with given minimum distance. Lower and upper bounds on the sizes of such codes are derived. In particular, we show tight connections between optimal codes and some known designs such as Howell designs, Kirkman squares, orthogonal arrays, Steiner systems, and large sets of Steiner systems. These optimal codes are natural generalization of Steiner systems and they are also called doubly Steiner systems. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 137–151, 2008     

Construction of optimal ternary constant weight codes via Bhaskar Rao designs

In this note, we consider a construction for optimal ternary constant weight codes (CWCs) via Bhaskar Rao designs (BRDs). The known existence results for BRDs are employed to generate many new optimal nonlinear ternary CWCs with constant weight 4 and minimum Hamming distance 5.     

Another complete invariant for Steiner triple systems of order 15

In this note, the 80 non‐isomorphic triple systems on 15 points are revisited from the viewpoint of the convex hull of the characteristic vectors of their blocks. The main observation is that the numbers, of facets of these 80 polyhedra are all different, thus producing a new proof of the non‐isomorphism of these triple systems. The space dimension of these polyhedra is also discussed. Finally, we observe the large number of facets of some of these polyhedra with few vertices, in relation with the upper bound problem for combinatorial polyhedra. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

More on regular linear spaces

We extend the enumeration of regular linear spaces in 1 to at most 19 points. In addition, one of the 5 missing cases in the previous list is settled. The number of regular linear spaces of type (15|2¹⁵,3³⁰) is 10,177,328. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

The Steiner quadruple systems of order 16

The Steiner quadruple systems of order 16 are classified up to isomorphism by means of an exhaustive computer search. The number of isomorphism classes of such designs is 1,054,163. Properties of the designs—including the orders of the automorphism groups and the structures of the derived Steiner triple systems of order 15—are tabulated. A consistency check based on double counting is carried out to gain confidence in the correctness of the classification.     

Risk models for the Prize Collecting Steiner Tree problems with interval data

Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c+e]while taking risk(c+e xe)/(c+e c e)of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p+v]for its inclusion in T while taking risk(yv p v)/(p+v p v)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.