Geri Dön

Graph partitioning and semi-definite programming hierarchies

Başlık çevirisi mevcut değil.

  1. Tez No: 403412
  2. Yazar: ALİ KEMAL SİNOP
  3. Danışmanlar: Dr. VENKAT GURUSWAMI
  4. Tez Türü: Doktora
  5. Konular: Matematik, İstatistik, Mathematics, Statistics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2012
  8. Dil: İngilizce
  9. Üniversite: Carnegie Mellon University
  10. Enstitü: Yurtdışı Enstitü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 187

Özet

Özet yok.

Özet (Çeviri)

Graph partitioning is a fundamental optimization problem that has been intensively studied. Many graph partitioning formulations are important as building blocks for divide-and-conquer algorithms on graphs as well as to many applications such as VLSI layout, packet routing in distributed networks, clustering and image segmentation. Unfortunately such problems are notorious for the huge gap between known best known approximation algorithms and hardness of approximation results. In this thesis, we study approximation algorithms for graph partitioning problems using a strong hierarchy of relaxations based on semi-definite programming, called Lasserre Hierachy. Our main contribution in this thesis is a propagation based rounding framework for solutions arising from such relaxations. We present a novel connection between the quality of solutions it outputs and column based matrix reconstruction problem. As part of our work, we derive optimal bounds on the number of columns necessary together with efficient randomized and deterministic algorithms to find such columns. Using this framework, we derive approximation schemes for many graph partitioning problems with running times dependent on how fast the graph spectrum grows. Our final contribution is a fast SDP solver for this rounding framework: Even though SDP relaxation has nO(r) many variables, we achieve running times of the form 2O(r) poly(n) by only partially solving the relevant part of relaxation. In order to achieve this, we present a new ellipsoid algorithm that returns certificate of infeasibility.

Benzer Tezler

  1. Mekansal-zamansal hasta hareketlilik verileriyle mekansal etkileşim örüntülerinin analizi ve akış haritaları aracı tasarımı ve geliştirilmesi

    Analysis of spatial interaction patterns using spatio temporal patient mobility data, and designing and developing a flow mapping tool

    SELMAN DELİL

    Doktora

    Türkçe

    Türkçe

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilişim Uygulamaları Ana Bilim Dalı

    PROF. DR. RAHMİ NURHAN ÇELİK

  2. Paralel matris işlemleri kütüphanesinin çizge bölümlemeye dayalı olarak gerçeklenmesi

    Parallel matrix library using graph partitioning

    ALİ ALP

    Yüksek Lisans

    Türkçe

    Türkçe

    2002

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Uluslararası Bilgisayar Ana Bilim Dalı

    PROF.DR. TURHAN TUNALI

  3. Hypergraph models for sparse matrix partitioning and reordering

    Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri

    ÜMİT VEYSEL ÇATALYÜREK

    Doktora

    İngilizce

    İngilizce

    1999

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Yazılımı Ana Bilim Dalı

    DOÇ. DR. CEVDET AYKANAT

  4. Polyhedral approaches to hypergraph partitioning and cell formation

    Hiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi

    LEVENT KANDİLLER