Some formulations for the group steiner tree problem

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V(G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R∈R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.     

A new class of facets for the Latin square polytope

Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAP_n). In this paper, we present a new class of facets for the associated polytope, induced by odd-hole inequalities.     

NEWMAN猜想的一个简单证明

本文研究了一个数论问题:Newman猜想.从连续整数m 1,m 2,…,m n组成的集合中选出n个子集合,运用组合数学方法,获得了Newman猜想的一个简单证明.     

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

On the number of zero-patterns of a sequence of polynomials

Let be a sequence of polynomials of degree in variables over a field . The zero-pattern of at is the set of those ( ) for which . Let denote the number of zero-patterns of as ranges over . We prove that for and

for . For , these bounds are optimal within a factor of . The bound () improves the bound proved by J. Heintz (1983) using the dimension theory of affine varieties. Over the field of real numbers, bounds stronger than Heintz's but slightly weaker than () follow from results of J. Milnor (1964), H.E.  Warren (1968), and others; their proofs use techniques from real algebraic geometry. In contrast, our half-page proof is a simple application of the elementary ``linear algebra bound'.

Heintz applied his bound to estimate the complexity of his quantifier elimination algorithm for algebraically closed fields. We give several additional applications. The first two establish the existence of certain combinatorial objects. Our first application, motivated by the ``branching program' model in the theory of computing, asserts that over any field , most graphs with vertices have projective dimension (the implied constant is absolute). This result was previously known over the reals (Pudlák-Rödl). The second application concerns a lower bound in the span program model for computing Boolean functions. The third application, motivated by a paper by N. Alon, gives nearly tight Ramsey bounds for matrices whose entries are defined by zero-patterns of a sequence of polynomials. We conclude the paper with a number of open problems.

     

Proper gromov transforms of metrics are metrics

In phylogenetic analysis, a standard problem is to approximate a given metric by an additive metric. Here it is shown that, given a metric D defined on some finite set X and a nonexpansive map f : X → , the one-parameter family of the Gromov transforms D^Δ,f of D relative to f and Δ that starts with D for large values of Δ and ends with an additive metric for Δ = 0 consists exclusively of metrics. It is expected that this result will help to better understand some standard tree reconstruction procedures considered in phylogenetic analysis.     

Long arithmetic progressions in critical sets

Given a density 0<σ?1, we show for all sufficiently large primes p that if S⊆Z/pZ has the least number of three-term arithmetic progressions among all sets with at least σp elements, then S contains an arithmetic progression of length at least log^1/4+o(1)p.     

Solving high-index DAEs by Taylor series

We present a general method of solving differential-algebraic equations by expanding the solution as a Taylor series. It seems especially suitable for (piecewise) smooth problems of high index. We describe the method in general, discuss steps to be taken if the method, as initially applied, fails because it leads to a system of equations with identically singular Jacobian, and illustrate by solving two problems of index 5. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the monotonization of polyhedra

In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing its facial structure. It is therefore customary to approach the study of such a polytopeP through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant ofP. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a polyhedronP, g-mon(P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet of g-mon(P) to define a facet ofP. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to define a facet of the original polytope itself. Research supported by grant DMI-9201340 of the National Science Foundation and contract N00014-89-J-1063 of the Office of Naval Research. Research supported by MURST, Italy.