FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Application of semidefinite and copositive programming in combinatorial optimization : doctoral thesis
    Povh, Janez, 1973-
    Semidefinitno in kopozitivno programiranje je postalo v zadnjih dveh desetletjih pomembno orodje v kombinatorični optimizaciji. Najdemo lahko mnogo problemov iz kombinatorične optimizacije, kjer so ... semidefinitni in kopozitivni aproksimacijski modeli mnogo boljši kot čisto linearni modeli. Za nekatere probleme celo velja, da lahko optimalno vrednost izrazimo kot rešitev kopozitivnega programa. Za semidefinitno programiranje imamo na razpolago mnogo učinkovitih metod za reševanje ne samo majhnih temveč tudi zelo velikih problemov, medtem ko za reševanje kopozitivnih problemov to ne drži. Kljub temu pa obstaja nekaj zadostnih pogojev za kopozitivnost, ki temeljijo na semidefinitnem programiranju in s pomočjo katerih lahko težko rešljive kopozitivne modele nadomestimo z lažje rešljivimi semidefinitnimi aproksimacijskimi modeli. V prvem delu disertacije predstavimo poleg nekaterih klasičnih, a za nadaljnje branje pomemnih, rezultatov iz linearne algebre in stožčne optimizacije tudi novo metodo za reševanje semidefinitnih programov. Ta metoda, ki smo jo poimenovali Metoda robnih točk, temelji na okrepljeni Lagrangeovi metodi (augmented Lagrangian method), z njo pa lahko rešimo probleme, ki so nerešljivi z metodami notranjih točk, če so le linearne enačbe iz semidefinitnega programa večinoma ortogonalne. V drugem delu disertacije prikažemo uporabo semidefinitnega in kopozitivnega programiranja pri reševanju naslednjih NP-težkih problemov iz kombinatorične optimizacije: problem pasovne širine grafa, problem kvadratičnega prirejanja, problem minimalnega prereza in problem delitve grafa. Na koncu pokažemo, kako lahko pristop k tem problemom razširimo še na nekatere druge 0-1 probleme kot so problem neodvisnega števila grafa in problem uravnoteženega ločilca grafa. Najprej predstavimo analizo algoritma za približno računanje pasovne širine grafa, objavljenega v "A.Blum, G.Konjevod, R.Ravi, S.Vempala: Semidefinite relaxations for minimum banwidth and othervertex-ordering problems. Theor. Comput. Sci., 235:25-42,2000", s posebnim povdarkom na izračunljivosti. Predlagamo tudi učinkovito strategijo za računanje tega algoritma, ki temelji na metodah notranjih točk. V nadaljevanju predstavimo način, kako zapisati probleme kvadratičnega prirejanja, minimalnega prereza in delitve grafa kot kopozitivni program v ustreznem višje dimenzionalnem prostoru. Z uporabo naraščajočega zaporedja stožcev, ki po točkah konvergira k stožcu kopozitivnih matrik, dobimo zaporedje semidefinitnih aproksimacijskih modelov za te probleme. Za vsak problem tudi pokažemo, da so že prvi modeli iz omenjenega zaporedja vsaj tako dobri kot nekateri drugi najboljši semidefinitni modeli.
    Vrsta gradiva - disertacija
    Založništvo in izdelava - Ljubljana : [J. Povh], 2006
    Jezik - angleški, slovenski
    COBISS.SI-ID - 14177113

Signatura – lokacija, inventarna št. ... Status izvoda Rezervacija
Skladišče-Jadranska 21

0000010921/0000000093 Skladišče-Jadranska 21

10921/93 		prosto - za čitalnico
loading ...
loading ...
loading ...

Vnos na polico