Analysis of online optimization problems in navigation and search on networks
Navigasyon ve arama konusunda çeşitli çevirimiçi eniyileme problemlerinin analizi
- Tez No: 544342
- Danışmanlar: PROF. DR. FATMA SİBEL SALMAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği ve Operasyon Yönetimi
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 123
Özet
In this thesis, we study online optimization problems that are related to navigation and search on networks. In online problems information is revealed incrementally, and decisions must be made before all information is available. We design and analyze strategies for several online problems with applications in disaster response, search-and-rescue, security, and defense. We prove worst-case competitive ratios to analyze the performance of the proposed strategies. We first study the online k-Canadian Traveler Problem (k-CTP) on O-D edge-disjoint graphs. An optimal randomized strategy was given in the literature. We prove that the given strategy cannot be implemented in some cases and modify it such that it is optimal and can be implemented in all cases. We consider the online multi-agent k-CTP. We derive improved lower bounds on the competitive ratio of deterministic strategies for the cases with limited and complete communication. We introduce two deterministic strategies and show that one of them is optimal in both cases with complete and limited communication on O-D edge-disjoint graphs. We provide lower bounds on the competitive ratio of randomized strategies for the cases without communication, with limited communication and with complete communication. We introduce a randomized online strategy which is optimal for both cases with limited and complete communication on O-D edge-disjoint graphs. We also consider the online Minimum Latency Problem with edge uncertainty. We present an optimal deterministic strategy. Moreover, we present a lower bound on the expected competitive ratio of randomized strategies. Finally, we investigate the online Discrete Search Problem with traveling and search costs on undirected graphs. We propose tight competitiveness lower bounds together with optimal deterministic and randomized strategies.
Özet (Çeviri)
Bu tezde, ağ yapıları üstünde navigasyon ve arama ile ilgili çeşitli çevrimiçi eniyileme problemleri üzerinde çalışılmıştır. Çevrimiçi problemlerde bilgiler adım adım açıklanır ve tüm bilgiler mevcut olmadan önce kararlar alınmalıdır. Tez kapsamında, afete müdahale, arama kurtarma, güvenlik ve savunma alanlarında uygulamaları olan birkaç çevrimiçi eniyileme problemi için eniyi stratejiler tasarlanıp bunların performansları teorik olarak analiz edilmiştir. Önerilen stratejilerin performanslarını analiz etmek için en kötü durumda, bilginin baştan elde olduğu (çevrimdışı) durumdaki en iyi çözüme göre, rekabetçi oranlar belirlenmiştir. İlk olarak, çevrimiçi k-Kanadalı Gezgin Problemi (k-KGP), ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenmiştir. Daha önce literatürde bu problem için bir eniyi rassal strateji verilmiştir. Bu çalışmada, bazı durumlarda bu stratejinin uygulanamaz olduğu gösterilerek, strateji her durumda uygulanabilir ve eniyi olacak şekilde değiştirilmiştir. Daha sonra çevrimiçi çok katılımcılı k-KGP ele alınmıştır. Bu problemin sınırlı ve sınırsız iletişimin olduğu iki durumuna bakılarak, literatürde verilen, deterministik stratejilerin rekabetçi oranına alt sınırı iyileştirilmiştir. Aynı iki durum, ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenerek, iki deterministik strateji geliştirilmiştir. Bunlardan bir tanesinin eniyi olduğu ispatlanmıştır. Problemin iletişimin olmadığı, sınırlı ve sınırsız iletişimin olduğu üç durumuna bakılarak, rassal stratejilerin rekabetçi oranına alt sınırlar geliştirilmiştir. Ayrıca iletişimli durumlar için rassal bir strateji geliştirilerek, bunun ayrıtları kesişmeyen yollara sahip çizgeler üzerinde eniyi olduğu ispatlanmıştır. Ayrıt belirsizliği olan çevrimiçi Minimum Gecikme Problemi de ele alınan bir başka problemdir. Bu problem için bir eniyi deterministik strateji geliştirilmiştir. Ayrıca, rassal stratejilerin beklenen rekabetçi oranına bir alt sınır bulunmuştur. Son olarak, çevrimiçi Ayrık Arama Problemi, yönlendirilmemiş çizgelerdeki seyahat ve arama maliyetleriyle incelenmiştir. Eniyi deterministik ve rassal stratejiler bulunmuştur.
Benzer Tezler
- Biyolojik işaretlerin gelişmiş bir sayısal işaret işlemcisiyle işlenmesi
Biomedical signal processing using a high performance DSP
DERYA DEMİR
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ERTUĞRUL YAZGAN
- Emergency and terminated evacuation of warehouse by dijkstra's algorithm
Dijkstra algoritması kullanılarak acil ve sınırlandırılmış depo tahliyesi
DENİZ DOĞA IŞIK
Yüksek Lisans
İngilizce
2024
Mühendislik Bilimleriİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ŞAZİYE ÖZGE ATİK
- Distributed algorithms based on fictitious play for near optimal sequential decision making
Başlık çevirisi yok
ESRA ŞİŞİKOĞLU
Doktora
İngilizce
2009
Endüstri ve Endüstri MühendisliğiUniversity of MichiganDOÇ. DR. MARINA A. EPELMAN
PROF. ROBERT L. SMITH
- Dizel motorların modellenmesi,modele dayalı hava yolu ve emisyon kontrolörü geliştirilmesi / uygulanması
Modeling of diesel engines, development and application of model based airpath and emission controllers
BÜLENT ÜNVER
Doktora
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. METİN GÖKAŞAN
PROF. DR. SETA BOGOSYAN
- Gıda renklendiricilerinin tayini için yeni yöntemler geliştirilmesi
Development of novel methods for the determination of food colorants
FATOŞ AYÇA ÖZDEMİR OLGUN
Doktora
Türkçe
2014
Kimyaİstanbul Teknik ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. BİRSEN DEMİRATA ÖZTÜRK