VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
Celotno besedilo
  • Towards the optimum by semidefinite and copositive programming : new approach to approximate hard optimization problems
    Povh, 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.
    Vrsta gradiva - znanstvena monografija ; neleposlovje za odrasle
    Založništvo in izdelava - Saarbrücken : VDM Verlag Dr. Müller, 2009
    Jezik - angleški
    ISBN - 978-3-639-16654-5
    COBISS.SI-ID - 15199833
Knjižnica/institucija Kraj Akronim Za izposojo Druga zaloga
Narodna in univerzitetna knjižnica, Ljubljana Ljubljana NUK v čitalnico 1 izv.
Univerzitetna knjižnica Maribor Maribor UKM v čitalnico 1 izv.
loading ...
loading ...