Approximation of the stability number of a graph via copositive programming

Approximation of the stability number of a graph via copositive programming

Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166–190] showed how to formulate increasingly tight approximations of the stable set polytope of a graph by solving semideﬁnite programs (SDPs) of increasing size (lift-and-project method). In this paper we present a similar idea. We show how the s...

Saved in:

書目詳細資料
Main Authors:	Klerk, Etienne de., Pasechnik, Dmitrii V.
其他作者:	School of Physical and Mathematical Sciences
格式:	Article
語言:	English
出版:	2011
主題:	DRNTU::Science::Mathematics::Applied mathematics
在線閱讀:	https://hdl.handle.net/10356/93758 http://hdl.handle.net/10220/6790
標簽:	添加標簽沒有標簽, 成為第一個標記此記錄!
機構:	Nanyang Technological University
語言:	English

相似書籍

A note on the stability number of an orthogonality graph
由: Klerk, Etienne de., et al.
出版: (2011)

Improved lower bounds on book crossing numbers of complete graphs
由: Salazar, G., et al.
出版: (2014)

Improved bounds for the crossing numbers of Km,n and Kn
由: Klerk, Etienne de., et al.
出版: (2011)

On semidefinite programming relaxations of the traveling salesman problem
由: De Klerk, Etienne., et al.
出版: (2009)

On approximate graph colouring and max-k-cut algorithms based on the θ-function
由: Klerk, Etienne de., et al.
出版: (2013)

On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs
由: Sotirov, R., et al.
出版: (2012)

Approximation of copositive programming via linear programming using second order sum of square decomposition
由: Thanasak Mouktonglang, et al.
出版: (2018)

A linear programming reformulation of the standard quadratic optimization problem
由: Klerk, Etienne de., et al.
出版: (2013)

Reduction of symmetric semidefinite programs using the regular representation
由: Klerk, Etienne de., et al.
出版: (2012)

Numerical block diagonalization of matrix - algebras with application to semidefinite programming
由: Klerk, Etienne de., et al.
出版: (2012)

Products of positive forms, linear matrix inequalities, and Hilbert 17th problem for ternary forms
由: Klerk, Etienne de., et al.
出版: (2012)

Polynomial-time computing over quadratic maps I : sampling in real algebraic sets
由: Grigoriev, Dima., et al.
出版: (2011)

Computing the nucleolus of weighted voting games
由: Pasechnik, Dmitrii V., et al.
出版: (2011)

On semidefinite programming relaxations of maximum k -section
由: Klerk, Etienne de., et al.
出版: (2013)

On the irreducibility of a truncated binomial expansion
由: Filaseta, Michael., et al.
出版: (2011)

A characterization of the Petersen-type geometry of the McLaughlin group
由: Baumeister, Barbara, et al.
出版: (2011)

Subsets close to invariant subsets for group actions
由: Brailovsky, Leonid., et al.
出版: (2011)

Affine extensions of the Petersen graph and 2-arc-transitive graphs of girth 5
由: Pasechnik, Dmitrii V.
出版: (2013)

The primal-dual second-order cone approximations algorithm for symmetric cone programming
由: Chua, Chek Beng.
出版: (2009)

On some locally 3-transposition graphs
由: Pasechnik, Dmitrii V.
出版: (2011)

On equicut graphs
由: Deza, Michel., et al.
出版: (2011)

Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n-1(4n-1)
由: Pasechnik, Dmitrii V.
出版: (2013)

On NP-hardness of the clique partition : independence number gap recognition and related problems
由: Busygin, Stanislav., et al.
出版: (2012)

Superconvergence for the gradient of finite element approximations by L2-projections
由: Heimsund, Bjorn-Ove, et al.
出版: (2009)

Exponential convergence of spectral approximations and time-domain computation of scattering problems.
由: Zhao, Xiaodan.
出版: (2013)

A local characterization of the graphs of alternating forms and the graphs of quadratic forms over GF(2)
由: Munemasa, A., et al.
出版: (2011)

Delay-dependent stability analysis of numerical methods for stochastic delay differential equations
由: Huang, Chengming, et al.
出版: (2013)

Using neural networks for approximating functions and equations
由: Li, Yongming
出版: (2019)

Generalised polynomial chaos approximation for stochastic fractional partial differential equations
由: Teh, Yu Xuan
出版: (2023)

On computing Hilbert bases via the Elliot–MacMahon algorithm
由: Pasechnik, Dmitrii V.
出版: (2012)

Leveraging approximation properties of neural networks for efficient bond pricing
由: Samay, Panwar
出版: (2023)

Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
由: Basu, Saugata, et al.
出版: (2009)

Compression methods for approximate stochastic modelling
由: Onggadinata, Kelvin
出版: (2020)

On the number of inductively minimal geometries
由: Cara, Philippe, et al.
出版: (2013)

Generalized Arithmetic Staircase Graphs and Their Total Edge Irregularity Strengths
由: Susanti, Yeni, et al.
出版: (2022)

Global stabilization of linear time-varying delay systems with bounded controls
由: Phat,V.N., et al.
出版: (2015)

Wiretap encoding of lattices from number fields using codes over Fp
由: Kositwattanarerk, Wittawat, et al.
出版: (2013)

Improved lower bounds for the 2-page crossing numbers of Km,n and Kn via semidefinite programming
由: Klerk, E. de., et al.
出版: (2013)

Application of dynamic programming in the minimal superpermutation problem
由: Ong, Linus Hong Jun
出版: (2020)

Approximation of copositive programming via linear programming using second order sum of square decomposition
由: Mouktonglang T., et al.
出版: (2017)