Minimum hub cover problem: Solution methods and applications
En küçük göbek kapsama problemi: Çözüm metodları ve uygulamalar
- Tez No: 389474
- Danışmanlar: PROF. DR. ŞEVKET İLKER BİRBİL, DOÇ. DR. KEREM BÜLBÜL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
En küçük göbek kapsama problemi, çizge veri tabanları üzerinde sorgulama alanında literatüre kazandırılmış yeni bir eniyileme problemidir. Problem, çizge sorgularının hızlandırılması için yeni bir çizge gösterim şekli olarak önerilmiştir. Bu gösterim şekli ile bir çizge veritabanı, o çizgenin düğümlerinin bir alt kümesi cinsinden ifade edilmektedir. Bu alt küme üzerinden sorgu işlemek, sorgu süresinin azalmasını ve sorgu sürecinin verimliliğinin artmasını sağlamaktadır. Bu çalışmada en az sayıda düğümle bir çizgeyi ifade etme problemini en küçük göbek kapsama problemi olarak tanımlıyoruz. Bu alt küme üzerinden sorgulama işlemi yapılmasının sorgu verimliliğini artırdığını ve mevcut yöntemlere göre avantaj sağladığını gösteriyoruz. Bu çalışmada en küçük göbek kapsama problemi içlerinde 0-1 tamsayılı programlama formülasyonu ile ikinci dereceden tamsayılı programla modelinin de olduğu farklı matematiksel programlama modelleri tanıtıyoruz. İkinci dereceden tamsayılı programlama modelinin gevşetilmesini kullanarak yarıbelgili programlama formülasyonu elde ediyoruz. Doğrusal ve yarıbelgili gevşetme modellerini kullanan yuvarlama yöntemleri önererek bu yöntemlerin deneysel performanslarını karşılaştırıyoruz. Ayrıca düzeysel çizge veri tabanlarında nesne tanımlama, biyometrik kimlik belirleme gibi sorgu işleme uygulamaları olan düzeysel çizgelere odaklanıp iyi çözümler üreten hızlı sezgisel geliştiriyoruz. En küçük göbek kapsama problemini düzeysel çizgeler üzerinde performans garantisi veren bir yaklaşıklama algoritması tanıtıyoruz. Çeşitli sayısal çalışmalar ile tezde önerilen çözüm yöntemlerinin deneysel performanslarını ölçüyoruz.
Özet (Çeviri)
The minimum hub cover is a new NP-hard optimization problem that has been recently introduced to the literature in the context of graph query processing on graph databases. The problem has been proposed as a new graph representation model to expedite graph queries. With this representation, a graph database can be represented by a small subset of graph vertices. Searching over only that subset of vertices decreases the response time of a query and increases the efficiency of graph query processing. We introduce the problem of finding a subgraph including the minimum number of vertices as an optimization problem referred to as the minimum hub cover problem. We demonstrate that searching a query over the vertices in minimum hub cover increases the efficiency of query processing and surpasses the existing search methods. We also introduce several mathematical programming models. In particular, we give two binary integer programming formulations as well as a novel quadratic integer programming formulation. We use the linear programming relaxations of the binary integer programming models. Our relaxation for the quadratic integer programming model leads to a semidefinite programming formulation. We also present several rounding heuristics to obtain integral solutions after solving the proposed relaxations. We also focus on planar graphs which have many applications in planar graph query processing and devise fast heuristics with good solution quality for minimum hub cover. We also study an approximation algorithm with a performance guarantee to solve the minimum hub cover problem on planar graphs. We conduct several numerical studies to analyze the empirical performances of solution methods proposed in this thesis.
Benzer Tezler
- H∞ model eşleme probleminin lineer matris eşitsizlikleri yaklaşımı ile çözümü
The solution of the H∞ model matching problem via linear matrix inequalities
MURAT AKIN
Doktora
Türkçe
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. LEYLA GÖREN
- Elektrikli bisikletler için fırçasız doğru akım motoru tasarımı ve üretimi
Design and implementation of brushless dc motor for electric bicycles
GAMZE TANÇ
Yüksek Lisans
Türkçe
2014
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖZGÜR ÜSTÜN
- Konteyner kapasite ve taşıma planlama politikalarının sistem dinamiği yaklaşımı ile modellemesi
The system dynamics modelling for container capacity & transportation planning policies
MEHMET ÇAĞATAY BAHADIR
Doktora
Türkçe
2020
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. HATİCE CAMGÖZ AKDAĞ
- Akım taşıyıcılı çok fonksiyonlu ikinci derece aktif filtre yapıları
Başlık çevirisi yok
AHMET İHSAN YÜCE
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ TOKER
- Ham petrol ve doğal gaz fiyatlarında oynaklık modellemesi
Volatility modelling in crude oil and natural gas prices
ÖMÜR SALTIK