-
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.Type of material - dissertationPublication and manufacture - Ljubljana : [J. Povh], 2006Language - english, slovenianCOBISS.SI-ID - 14177113
Author
Povh, Janez, 1973-
Other authors
Rendl, Franz |
Mohar, Bojan, 1956- |
Juvan, Martin
Topics
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
Library | Call number – location, accession no. ... | Copy status |
---|---|---|
National and University Library, Ljubljana | GS II 625311 glavno skladišče | available - reading room |
Central Technological Library of the University of Ljubljana | 52047/1684 Skladišče IN: 320070086 |
available - outside loan, loan period: 14 days |
FMF, Mathematical Library, Lj. | Skladišče-Jadranska 21 10921/93 |
available - reading room |
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Povh, Janez, 1973- | 22649 |
Rendl, Franz | |
Mohar, Bojan, 1956- | 01931 |
Juvan, Martin | 11220 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.