-
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
semidefinitno programiranje |
kopozitivno programiranje |
metoda robnih točk |
kombinatorična optimizacija |
problem kombinatoričnega prirejanja |
problem minimalnega prereza |
problem delitve grafa |
problem pasovnosti grafa |
semidefinite programming |
copositive programming |
boundary point method |
combinatorial optimization |
quadratic assignment problem |
min-cat problem |
graph partitioning problem |
bandwidth problem
Knjižnica/institucija |
Kraj | Akronim | Za izposojo | Druga zaloga |
---|---|---|---|---|
Centralna tehniška knjižnica Univerze v Ljubljani | Ljubljana | CTK |
na dom 1 izv.
|
|
FMF in IMFM, Matematična knjižnica, Ljubljana | Ljubljana | MAKLJ |
v čitalnico 1 izv.
|
|
Narodna in univerzitetna knjižnica, Ljubljana | Ljubljana | NUK |
v čitalnico 1 izv.
|
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.