共查询到20条相似文献,搜索用时 46 毫秒
1.
The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that
restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair
of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics.
Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002
RID="★"
ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired
in part with support from NSF Grant DMS-9872009.
Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous
optimization heuristics – nonlinear programming
Mathematics Subject Classification (2000): 90C06, 90C27, 90C30 相似文献
2.
P. M. Kleniati P. Parpas B. Rustem 《Journal of Optimization Theory and Applications》2010,145(2):289-310
We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim.
17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series
of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based
method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose
is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci.
2(1):3–19, 2005). 相似文献
3.
The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous
bounds on the chromatic number χ(G) or the clique number ω(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming
formulation can be tightened toward either χ(G) or ω(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed
with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism
groups.
Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged. 相似文献
4.
The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number
of G. We introduce a related strengthening of the Lovász theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NP-hard. This motivates the study of tractable approximations of the copositive cone. We
investigate the Parrilo hierarchy to approximate this cone and provide computational simplifications for the approximation
of the chromatic number of vertex transitive graphs. We provide some computational results indicating that the Lovász theta
number can be strengthened significantly toward the fractional chromatic number of G on some Hamming graphs.
Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged. 相似文献
5.
Monique Laurent 《Mathematical Programming》2007,109(2-3):239-261
We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras.
The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located
between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with
O(n
7) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n
3), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s
bound with the same computational complexity.
Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203. 相似文献
6.
Adam Kurpisz Monaldo Mastrolilli Claire Mathieu Tobias Mömke Victor Verdugo Andreas Wiese 《Mathematical Programming》2018,172(1-2):231-248
Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász and Schrijver (SIAM J Optim 1:166–190, 1991) developed systematic procedures to construct the hierarchies of relaxations known as lift-and-project methods. They have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. Then we show that for any integer n there is an instance with n jobs in this family such that after \(\varOmega (n)\) rounds of the Sherali–Adams (\(\text {SA}\)) or the Lovász–Schrijver (\(\text {LS}_+\)) hierarchy the integrality gap remains at least 1024/1023. 相似文献
7.
R. Pendavingh 《Combinatorica》1998,18(2):281-292
, where μ and λ are minor-monotone graph invariants introduced by Colin de Verdière [3] and van der Holst, Laurent, and Schrijver
[5]. It is also shown that a graph G exists with . The graphs G with maximal planar complement and , characterised by Kotlov, Lovász, and Vempala, are shown to be forbidden minors for .
Received: June 13, 1997 相似文献
8.
Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for 0/1 linear programming problems. We revisit these two constructions and propose two new, block-diagonal hierarchies, which are at least as strong as the Lovász-Schrijver hierarchy, but less costly to compute. We report experimental results for the stable set problem of Paley graphs. 相似文献
9.
Monia Giandomenico Adam N. Letchford Fabrizio Rossi Stefano Smriglio 《Mathematical Programming》2009,120(2):381-401
Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin
with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the
operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe
the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results.
Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.
相似文献
10.
Carlos J. Luz 《Linear algebra and its applications》2007,423(1):99-108
It is well known that the ratio bound is an upper bound on the stability number α(G) of a regular graph G. In this note it is proved that, if G is a graph whose edge is a union of classes of a symmetric association scheme, the Delsarte’s linear programming bound can alternatively be stated as the minimum of a set of ratio bounds. This result follows from a recently established relationship between a set of convex quadratic bounds on α(G) and the number ?′(G), a well known variant of the Lovász theta number, which was introduced independently by Schrijver [A. Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory 25 (1979) 425-429] and McEliece et al. [R.J. McEliece, E.R. Rodemich, H.C. Rumsey Jr, The Lovász bound and some generalizations, J. Combin. Inform. System Sci. 3 (1978) 134-152]. 相似文献
12.
In this note we adopt the approach in Bonnit et al. (Czechoslov. Math. J. 60(2):527–539, 2010) to give a direct proof of some recent results in Haak and Le Merdy (Houst. J. Math., 2005) and Haak and Kunstmann (SIAM J. Control Optim. 45:2094–2118, 2007) which characterizes the L
p
-admissibility of type α depending on p of unbounded observation operators for bounded analytic semigroups. 相似文献
13.
Ear Decompositions of Matching Covered Graphs 总被引:3,自引:0,他引:3
G different from and has at least Δ edge-disjoint removable ears, where Δ is the maximum degree of G. This shows that any matching covered graph G has at least Δ! different ear decompositions, and thus is a generalization of the fundamental theorem of Lovász and Plummer
establishing the existence of ear decompositions. We also show that every brick G different from and has Δ− 2 edges, each of which is a removable edge in G, that is, an edge whose deletion from G results in a matching covered graph. This generalizes a well-known theorem of Lovász. We also give a simple proof of another
theorem due to Lovász which says that every nonbipartite matching covered graph has a canonical ear decomposition, that is,
one in which either the third graph in the sequence is an odd-subdivision of or the fourth graph in the sequence is an odd-subdivision of . Our method in fact shows that every nonbipartite matching covered graph has a canonical ear decomposition which is optimal,
that is one which has as few double ears as possible. Most of these results appear in the Ph. D. thesis of the first author
[1], written under the supervision of the second author.
Received: November 3, 1997 相似文献
14.
Vojtěch Rödl 《Combinatorica》1982,2(4):377-383
P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every
subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3.
The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The
first was done also by L. Lovász who used a different construction. 相似文献
15.
We study the Lovász–Schrijver lift-and-project operator (\({{\mathrm{\text {LS}}}}_+\)) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the \({{\mathrm{\text {LS}}}}_+\)-operator generates the stable set polytope in one step has been open since 1990. We call these graphs \({{{\mathrm{\text {LS}}}}}_+\)-perfect. In the current contribution, we pursue a full combinatorial characterization of \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs. 相似文献
16.
Jelena Govorčin Nebojša Gvozdenović Janez Povh 《Central European Journal of Operations Research》2013,21(1):13-25
The Lovász theta number Lovász (IEEE Trans Inf Theory 25:1–7, 1979) is a well-known lower bound on the chromatic number of a graph \(G\), and \(\varPsi _K(G)\) is its impressive strengthening Gvozdenovi? and Laurent (SIAM J Optim 19(2):592–615, 2008). The bound \(\varPsi _K(G)\) was introduced in very specific and abstract setting which is tough to translate into usual mathematical programming framework. In the first part of this paper we unify the motivations and approaches to both bounds and rewrite them in a very similar settings which are easy to understand and straightforward to implement. In the second part of the paper we provide explanations how to solve efficiently the resulting semidefinite programs and how to use optimal solutions to get good coloring heuristics. We propose two vertex coloring heuristics based on \(\varPsi _K(G)\) and present numerical results on medium sized graphs. 相似文献
17.
Alexander Engström 《Discrete and Computational Geometry》2008,40(3):357-364
The Hom complexes were introduced by Lovász to study topological obstructions to graph colorings. The vertices of Hom(G,K
n
) are the n-colorings of the graph G, and a graph coloring is a partition of the vertex set into independent sets. Replacing the independence condition with any
hereditary condition defines a set partition complex. We show how coloring questions arising from, for example, Ramsey theory
can be formulated with set partition complexes.
It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that Hom(G,K
n
) is (n−d−2)-connected, where d is the maximal degree of a vertex of G. We generalize this to set partition complexes. 相似文献
18.
V. Gupta 《Ukrainian Mathematical Journal》2005,57(12):1892-1900
We estimate the rate of convergence for functions of bounded variation for the Bézier variant of the Szász operators S
n,α
(f,x). We study the rate of convergence of S
n,α
(f,x) in the case 0 < α < 1.
Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 12, pp. 1619–1624, December, 2005. 相似文献
19.
For any two graphs F and G, let hom(F,G) denote the number of homomorphisms F→G, that is, adjacency preserving maps V(F)→V(G) (graphs may have loops but no multiple edges). We characterize graph parameters f for which there exists a graph F such that f(G)=hom(F,G) for each graph G.The result may be considered as a certain dual of a characterization of graph parameters of the form hom(.,H), given by Freedman, Lovász and Schrijver [M. Freedman, L. Lovász, A. Schrijver, Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007) 37-51]. The conditions amount to the multiplicativity of f and to the positive semidefiniteness of certain matrices N(f,k). 相似文献
20.
V. M. Kopytov 《Algebra and Logic》2009,48(5):344-356
We create a method which allows an arbitrary group G with an infrainvariant system ℒ(G) of subgroups to be embedded in a group G* with an infrainvariant system ℒ(G*) of subgroups, so that G
α* ∩G ∈ ℒ(G) for every subgroup G
α* ∩G ∈ ℒ(G*) and each factor B/A of a jump of subgroups in ℒ(G*) is isomorphic to a factor of a jump in ℒ(G), or to any specified group H. Using this method, we state new results on right-ordered groups. In particular, it is proved that every Conrad right-ordered
group is embedded with preservation of order in a Conrad right-ordered group of Hahn type (i.e., a right-ordered group whose
factors of jumps of convex subgroups are order isomorphic to the additive group ℝ); every right-ordered Smirnov group is embedded
in a right-ordered Smirnov group of Hahn type; a new proof is given for the Holland–McCleary theorem on embedding every linearly
ordered group in a linearly ordered group of Hahn type. 相似文献