共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-joins and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behavior of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph depending linearly on the size of and involving the depth of a decomposition tree of in terms of basic perfect graphs. 相似文献
3.
4.
Doklady Mathematics - 相似文献
5.
6.
Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope. 相似文献
7.
We disprove the longstanding conjecture that every combinatorial automorphism of the boundary complex of a convex polytope
in euclidean spaceE
d
can be realised by an affine transformation ofE
d
. 相似文献
8.
Mathematical Programming - We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance... 相似文献
9.
This paper concerns the extension complexity of the Minimum Spanning Tree problem on a complete graph with nodes. The best known lower bound is the trivial bound, , the best known upper bound is the extended formulation size (Wong 1980, Martin 1991). We give a nondeterministic communication protocol with cost for the support of the spanning tree slack matrix. 相似文献
10.
《Operations Research Letters》2021,49(6):896-901
The hyperplane separation bound is a lower bound on the extension complexity of a polytope. It is the main tool in Rothvoß's proof of an exponential bound for the matching polytope (Rothvoß, 2017). We show that the technique is sensitive to the choice of slack matrix and does not improve upon the best known lower bounds for spanning tree and completion time polytopes when applied to their canonical slack matrices. Stronger bounds may be obtained by appropriate rescalings and redundancy. 相似文献
11.
Magelone Kömhoff 《Geometriae Dedicata》1980,9(1):73-76
Shephard [6] posed the problem of whether every combinatorial type of d-polytope can be represented by some subpolytope of some d-stack. Here we show that, at least in the case d=3, the answer to that problem is in the affirmative.I am indebted to Professor G.C. Shephard for reading a preliminary version of this note and making suggestions for its improvement. 相似文献
12.
Michael J. Todd 《Journal of Combinatorial Theory, Series B》1976,20(3):229-242
Primoids and duoids are collections of subsets of a fixed finite set with a natural generalization of a pivoting property of convex polytopes. This structure is precisely what is necessary for the application of complementary pivoting algorithms. This paper investigates the combinatorial structure of primoids and duoids, showing them to form the circuits and cocircuits of a binary matroid. This matroid is then compared with the simplicial geometries of Crapo and Rota. 相似文献
13.
Matthias Reitzner 《Advances in Mathematics》2005,191(1):178-208
Choose n random points in , let Pn be their convex hull, and denote by fi(Pn) the number of i-dimensional faces of Pn. A general method for computing the expectation of fi(Pn), i=0,…,d−1, is presented. This generalizes classical results of Efron (in the case i=0) and Rényi and Sulanke (in the case i=d−1) to arbitrary i. For random points chosen in a smooth convex body a limit law for fi(Pn) is proved as n→∞. For random points chosen in a polytope the expectation of fi(Pn) is determined as n→∞. This implies an extremal property for random points chosen in a simplex. 相似文献
14.
Using Frobenius partitions we extend the main results of [4]. This leads to an infinite family of 4-way combinatorial identities. In some particular cases we get even 5-way combinatorial identities which give us four new combinatorial versions of Göllnitz-Gordon identities. 相似文献
15.
Jean-Philippe Labbé Thibault Manneville Francisco Santos 《Mathematical Programming》2017,165(2):663-688
In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340–1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound \(O(n2^d)\) for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound \(n-d+1\) if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent but more local, by introducing the notions of monotonicity and conservativeness of dual paths in pure simplicial complexes. We use these definitions to investigate further properties of combinatorial segments. Besides recovering the two stated bounds, we show a refined bound for banner complexes, and study the behavior of the maximal length of combinatorial segments with respect to two usual operations, namely join and one-point suspension. Finally, we show the limitations of combinatorial segments by constructing pure normal simplicial complexes in which all combinatorial segments between two particular facets achieve the length \(\Omega (n2^{d})\). This includes vertex-decomposable—therefore Hirsch—polytopes. 相似文献
16.
《Discrete Mathematics》2006,306(10-11):886-904
17.
On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes 总被引:1,自引:0,他引:1
It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n2). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n). 相似文献
18.
Carl W. Lee 《Israel Journal of Mathematics》1984,47(4):261-269
Letf(P
s
d
) be the set of allf-vectors of simpliciald-polytopes. ForP a simplicial 2d-polytope let Σ(P) denote the boundary complex ofP. We show that for eachf ∈f(P
s
d
) there is a simpliciald-polytopeP withf(P)=f such that the 11 02 simplicial diameter of Σ(P) is no more thanf
0(P)−d+1 (one greater than the conjectured Hirsch bound) and thatP admits a subdivision into a simpliciald-ball with no new vertices that satisfies the Hirsch property. Further, we demonstrate that the number of bistellar operations
required to obtain Σ(P) from the boundary of ad-simplex is minimum over the class of all simplicial polytopes with the samef-vector. This polytopeP will be the one constructed to prove the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes. 相似文献
19.
Geometriae Dedicata - 相似文献
20.
On the complexity of a class of combinatorial optimization problems with uncertainty 总被引:2,自引:0,他引:2
Igor Averbakh 《Mathematical Programming》2001,90(2):263-272
We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})2
m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is
NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This
is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented
uncertainty but is polynomially solvable in the case of the interval representation of uncertainty.
Received: July 1998 / Accepted: May 2000?Published online March 22, 2001 相似文献