Graph partitioning and semi-definite programming hierarchies
Başlık çevirisi mevcut değil.
- Tez No: 403412
- Danışmanlar: Dr. VENKAT GURUSWAMI
- Tez Türü: Doktora
- Konular: Matematik, İstatistik, Mathematics, Statistics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: İngilizce
- Üniversite: Carnegıe Mellon Unıversıty
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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
- Feature-aware partitioning of quadrilateral meshes for reverse engineering
Başlık çevirisi yok
ERKAN GÜNPINAR
- 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
- Graph and hypergraph partitioning
Çizge ve hiperçizge parçalama
ALİ DAŞDAN
Yüksek Lisans
İngilizce
1993
İhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Yükleniyor...
- Combinatorial reductions between graph partitioning by vertex separator and hypergraph partitioning problems for parallel and scientific computing applications
Paralel ve bilimsel hesaplama uygulamaları için hiperçizge bölümleme ve düğüm ayıracı ile çizge bölümleme problemlerinin birbirine kombinatoriyal dönüştürümü
ENVER KAYAASLAN
Yüksek Lisans
İngilizce
2009
İhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
Yükleniyor...
- Graph/hypergraph partitioning models for simultaneous load balancing on computation and data
Eş zamanlı hesaplama ve veri yükü dengeleme için çizge/hiperçizge bölümleme modelleri
MESTAN FIRAT ÇELİKTUĞ
Yüksek Lisans
İngilizce
2018
İhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Yükleniyor...
