Geri Dön

Minimum hub cover problem: Solution methods and applications

En küçük göbek kapsama problemi: Çözüm metodları ve uygulamalar

  1. Tez No: 389474
  2. Yazar: BELMA YELBAY
  3. Danışmanlar: PROF. DR. ŞEVKET İLKER BİRBİL, DOÇ. DR. KEREM BÜLBÜL
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 127

Ö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

  1. 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

    Türkçe

    2014

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ÖZGÜR ÜSTÜN

  2. 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

    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Ğ

  3. Ham petrol ve doğal gaz fiyatlarında oynaklık modellemesi

    Volatility modelling in crude oil and natural gas prices

    ÖMÜR SALTIK

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    EkonomiDokuz Eylül Üniversitesi

    İktisat Ana Bilim Dalı

    DOÇ. DR. MERT URAL

  4. Rüzgar türbini göbeğinin yapısal tasarımı ve optimizasyonu

    Structural design and optimization of wind turbine hub

    SERKAN DEMİRCİ

    Yüksek Lisans

    Türkçe

    Türkçe

    2011

    Mühendislik BilimleriKocaeli Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. MURAT MAKARACI

  5. Hub location problem for air-ground transportation systems with time restrictions

    Hava ve kara taşımacılık sisteminde zaman kısıtlı ana dağıtım üssü yer seçimi problemi

    SEDA ELMASTAŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    2006

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    Y.DOÇ. BAHAR YETİŞ KARA

    Y.DOÇ. HANDE YAMAN