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. 相似文献
Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAPn). In this paper, we present a new class of facets for the associated polytope, induced by odd-hole inequalities. 相似文献
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.
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. 相似文献
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 log1/4+o(1)p. 相似文献
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. 相似文献
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. 相似文献