-
Towards the optimum by semidefinite and copositive programming : new approach to approximate hard optimization problemsPovh, Janez, 1973-V prvem delu monografije 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 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 Blum et al., 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, predlaganega s strani De Klerka, Pasechnika, 2002 in Parrila, 2000, 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 najboljši semidefinitni modeli iz literature.Type of material - scientific monograph ; adult, seriousPublication and manufacture - Saarbrücken : VDM Verlag Dr. Müller, 2009Language - englishISBN - 978-3-639-16654-5COBISS.SI-ID - 15199833
Author
Povh, Janez, 1973-
Topics
Semidefinitno programiranje |
semidefinitno programiranje |
kopozitivno programiranje |
metoda robnih točk |
kombinatorična optimizacija |
problem kvadratičnega prirejanja |
problem minimalnega prereza |
problem delitve grafa |
problem pasovnosti grafa |
semidefinite programming |
copositive programming |
boundary point method |
combinatorial optimization |
quadratic assignment problem |
min cut problem |
graph partitioning problem |
bandwidth problem
Library/institution |
City | Acronym | For loan | Other holdings |
---|---|---|---|---|
National and University Library, Ljubljana | Ljubljana | NUK |
reading room 1 cop.
|
|
University of Maribor Library | Maribor | UKM |
reading room 1 cop.
|
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 |
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.