ridm@nrct.go.th   ระบบคลังข้อมูลงานวิจัยไทย   รายการโปรดที่คุณเลือกไว้

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

หน่วยงาน Nanyang Technological University, Singapore

รายละเอียด

ชื่อเรื่อง : Approximation of the stability number of a graph via copositive programming.
นักวิจัย : Klerk, Etienne de. , Pasechnik, Dmitrii V.
คำค้น : DRNTU::Science::Mathematics::Applied mathematics.
หน่วยงาน : Nanyang Technological University, Singapore
ผู้ร่วมงาน : -
ปีพิมพ์ : 2545
อ้างอิง : 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. , http://hdl.handle.net/10220/6790 , http://dx.doi.org/10.1137/S1052623401383248
ที่มา : -
ความเชี่ยวชาญ : -
ความสัมพันธ์ : SIAM journal on optimization
ขอบเขตของเนื้อหา : -
บทคัดย่อ/คำอธิบาย :

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.

บรรณานุกรม :
Klerk, Etienne de. , Pasechnik, Dmitrii V. . (2545). Approximation of the stability number of a graph via copositive programming..
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Klerk, Etienne de. , Pasechnik, Dmitrii V. . 2545. "Approximation of the stability number of a graph via copositive programming.".
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Klerk, Etienne de. , Pasechnik, Dmitrii V. . "Approximation of the stability number of a graph via copositive programming.."
    กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2545. Print.
Klerk, Etienne de. , Pasechnik, Dmitrii V. . Approximation of the stability number of a graph via copositive programming.. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2545.