The General Routing Problem (GRP) consists of finding a minimum length closed walk in an edge-weighted undirected graph, subject to containing certain sets of required nodes and edges. It is related to the Rural Postman Problem and the Graphical Traveling Salesman Problem.We examine the 0/1-polytope associated with the GRP introduced by Ghiani and Laporte [A branch-and-cut algorithm for the Undirected Rural Postman Problem, Math. Program. Ser. A 87 (3) (2000) 467-481]. We show that whenever it is not full-dimensional, the set of equations and facets can be characterized, and the polytope is isomorphic to the full-dimensional polytope associated with another GRP instance which can be obtained in polynomial time. We also offer a node-lifting method. Both results are applied to prove the facet-defining property of some classes of valid inequalities. As a tool, we study more general polyhedra associated to the GRP. 相似文献
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.