mirage

Approximation of the stability number of a graph via copositive programming.

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

Approximation of the stability number of a graph via copositive programming.

Show simple item record

dc.contributor.author Klerk, Etienne de.
dc.contributor.author Pasechnik, Dmitrii V.
dc.date.accessioned 2011-05-11T04:43:16Z
dc.date.available 2011-05-11T04:43:16Z
dc.date.copyright 2002
dc.date.issued 2011-05-11T04:43:16Z
dc.identifier.citation Klerk, E. D., & Pasechnik, D. V. (2002). Approximation of the stability number of a graph via copositive programming. SIAM journal on optimization, 12(4), 875-892.
dc.identifier.uri http://hdl.handle.net/10220/6790
dc.description.abstract 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 semidefinite programs (SDPs) of increasing size (lift-and-project method). In this paper we present a similar idea. We show how the stability number can be computed as the solution of a conic linear program (LP) over the cone of copositive matrices. Subsequently, we show how to approximate the copositive cone ever more closely via a hierarchy of linear or semidefinite programs of increasing size (liftings). The latter idea is based on recent work by Parrilo [Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000]. In this way we can compute the stability number α(G) of any graph G(V, E) after at most α(G)2 successive liftings for the LP-based approximations. One can compare this to the n - α(G) - 1 bound for the LP-based lift-and-project scheme of Lovász and Schrijver. Our approach therefore requires fewer liftings for families of graphs where a(G) < O(√n). We show that the first SDP-based approximation for α(G) in our series of increasingly tight approximations coincides with the ϑ’function of Schrijver [IEEE Trans. Inform. Theory, 25 (1979), pp. 425–429]. We further show that the second approximation is tight for complements of triangle-free graphs and for odd cycles.
dc.language.iso en
dc.relation.ispartofseries SIAM journal on optimization
dc.rights © 2002 SIAM This paper was published in SIAM Journal on Optimization and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at: [DOI: http://dx.doi.org/10.1137/S1052623401383248]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.
dc.subject DRNTU::Science::Mathematics::Applied mathematics.
dc.title Approximation of the stability number of a graph via copositive programming.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.doi http://dx.doi.org/10.1137/S1052623401383248
dc.description.version Published version

Files in this item

Files Size Format View
19. Approximati ... copositive programming.pdf 200.2Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Statistics

Total views

All Items Views
Approximation of the stability number of a graph via copositive programming. 1107

Total downloads

All Bitstreams Views
19. Approximation of the stability number of a graph via copositive programming.pdf 659

Top country downloads

Country Code Views
Singapore 207
United States of America 167
China 78
Germany 42
Japan 19

Top city downloads

city Views
Singapore 205
Mountain View 78
Beijing 45
Tokyo 13
Jersey City 11

Downloads / month

  2014-09 2014-10 2014-11 total
19. Approximation of the stability number of a graph via copositive programming.pdf 0 0 14 14