UNI-MB - logo
UMNIK - logo
 
FMF, Mathematical Library, Lj. (MAKLJ)
  • Semidefinitno programiranje in kombinatorična optimizacija : magistrsko delo
    Povh, Janez
    Pri semidefinitnem programiranju iščemo optimum linearne funkcije na konveksni množici, sestavljeni iz pozitivno semidefinitnih matrik, katerih elementi zadoščajo dodatnim linearnim pogojem. Za te ... probleme je mogoče izpeljati bogato (čeprav ne tako kot pri linearnem programiranju) dualno teorijo, kar je jedro prvega poglavja. Ob nekaterih (ne preveč omejujočih) dodatnih predpostavkah je mogoče dokazati, da elipsoudna metoda reši problem demidefinitnega programiranja v polinomskem času. V praksi se od elipsoidne metode mnogo boljše obnesejo metode notranjih točk. V delu so natančneje predstavljene primarno-dualne metode, ki sledijo središčni poti. Semidefinitno programiranje omogoča (približno) reševanje mnogih (tudi NP-težkih) problemov. V zadnjih dveh poglavjih sta predstavljena algoritma za približno barvanje grafa in računanje pasovnosti grafa.
    Type of material - master's thesis ; adult, serious
    Publication and manufacture - Ljubljana : [J. Povh], 2002
    Language - slovenian
    COBISS.SI-ID - 11479385

Call number – location, accession no. ... Copy status Reservation
Skladišče-Jadranska 21

0000010941/0000000110
Skladišče-Jadranska 21

10941/110
available - reading room
loading ...
loading ...
loading ...