-
Application of semidefinite and copositive programming in combinatorial optimization : doctoral thesisPovh, 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 - disertacijaZaložništvo in izdelava - Ljubljana : [J. Povh], 2006Jezik - angleški, slovenskiCOBISS.SI-ID - 14177113
Avtor
Povh, Janez, 1973-
Drugi avtorji
Rendl, Franz |
Mohar, Bojan, 1956- |
Juvan, Martin
Teme
matematika |
operacijsko raziskovanje |
semidefinitno programiranje |
kopozitivno programiranje |
metoda robnih točk |
kombinatorična optimizacija |
problem kombinatoričnega prirejanja |
problem minimalnega prereza |
problem delitve grafa |
problem pasovnosti grafa |
doktorske disertacije
Rezervirajte gradivo na želenem mestu prevzema.
Mesto prevzema |
Status gradiva | Rezervacija |
---|---|---|
Centralna tehniška knjižnica Univerze v Ljubljani |
|
Signatura – lokacija, inventarna št. ... |
Status izvoda |
---|---|
0000052047/0000001684 Skladišče IN: 320070086 52047/1684 Skladišče IN: 320070086 |
prosto - na dom, čas izposoje: 14 dni
|
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Povh, Janez, 1973- | 22649 |
Rendl, Franz | |
Mohar, Bojan, 1956- | 01931 |
Juvan, Martin | 11220 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.