Problem liczby skoków w zbiorach częściowo uporządkowanych. Kombinatoryczne algorytmy aproksymacyjne, przeszukiwanie wyczerpujące i złożoność obliczeniowa

University of Warsaw Repository

pl | en
 
 

Show simple item record

dc.contributor.advisor Sysło, Maciej
dc.contributor.author Krysztowiak, Przemysław
dc.date.accessioned 2014-10-31T15:46:46Z
dc.date.available 2014-10-31T15:46:46Z
dc.date.issued 2014-10-31
dc.identifier.uri https://depotuw.ceon.pl/handle/item/833
dc.description.abstract Głównym problemem rozprawy doktorskiej jest minimalizacja liczby skoków posetu. Problem skoków dla danego posetu P polega na znalezieniu rozszerzenia liniowego, które minimalizuje liczbę sąsiadujących par elementów, nieporównywalnych w P. NP-trudność tego problemu została najpierw wykazana przez Pulleyblanka [56], a nastepnie na posetach przedziałowych przez Mitas [52]. Proponujemy kilka nowych algorytmów dla tego problemu. Najwięcej uwagi poświęcamy posetom przedziałowym. Dla posetów przedziałowych w latach 90-tych zaproponowano trzy wielomianowe algorytmy aproksymacyjne o współczynniku 3/2. Głównym rezultatem rozprawy jest przełamanie tego współczynnika. Poprawiamy algorytm podany przez Mitas i otrzymujemy aproksymację ze współczynnikiem 1.484. Ponadto przedstawiamy algorytm genetyczny dla problemu skoków na posetach przedziałowych, a także szybki algorytm dokładny dla tej klasy. W przypadku ogólnym, prezentujemy adaptację algorytmu przeszukiwania z zakazami działającą w oparciu o półsilnie zachłanne rozszerzenia liniowe, sformułowane przez Sysłę. Podejmujemy również temat posetów dwuwymiarowych. W klasie dwuwymiarowych posetów przedziałowych otrzymujemy algorytm aproksymacyjny dla problemu skoków ze współczynnikiem 4/3. Praktyczna część pracy obejmuje eksperymentalną analizę wydajności algorytmów przybliżajacych liczbę skoków.
dc.description.abstract The main problem considered in this thesis is to minimize the jump number of a poset. The jump number problem for a given poset P is to find a linear extension minimizing the number of adjacent pairs which are incomparable in P. NP-hardness of this problem was first established by Pulleyblank [56], and later for interval orders by Mitas [52]. In the thesis, some new algorithms for this problem are proposed. We focus mainly on interval orders. In the 1990’s, three polynomial-time approximation algorithms have been given for interval orders with approximation ratio of 3/2. The main result of this thesis is an improvement of this approximation ratio. We enhance the algorithm given by Mitas and we obtain a 1.484-approximation algorithm. Moreover, we present a genetic algorithm for the jump number problem on interval orders, and a fast exact algorithm for this class. In the general case, we present an adaptation of the tabu search technique, based on semi-strongly greedy linear extensions, defined by Sysło. We also undertake the jump number of two-dimensional orders. We obtain a 4/3-approximation algorithm for the class of two-dimensional interval orders. In addition, the thesis contains an experimental analysis of efficiency of algorithms to approximate the jump number.
dc.language.iso pl
dc.rights info:eu-repo/semantics/restrictedAccess
dc.subject set cover
dc.subject subgraph packing
dc.subject approximation algorithm
dc.subject combinatorial optimization
dc.subject jump number
dc.subject pokrycie zbioru
dc.subject pakowanie podgrafów
dc.subject algorytm aproksymacyjny
dc.subject optymalizacja kombinatoryczna
dc.subject liczba skoków
dc.title Problem liczby skoków w zbiorach częściowo uporządkowanych. Kombinatoryczne algorytmy aproksymacyjne, przeszukiwanie wyczerpujące i złożoność obliczeniowa
dc.type info:eu-repo/semantics/doctoralThesis
dc.description.eperson Przemysław Krysztowiak
dc.contributor.department Wydział Matematyki, Informatyki i Mechaniki
dc.date.defence 2014-11-20

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Repository


Advanced Search

Browse

My Account

Statistics