Next: About this document
Up: No Title
Previous: No Title
-
Suunnittele pyöristystekniikkaan (LP-relaksaatioon) perustuva satunnaistettu
approksimointialgoritmi MAX WEIGHTED CLIQUE -optimointiongelmalle
(klikkiongelma, jossa verkon kaarilla on painot). Mitään
approksimointitakuuta algoritmille ei tarvitse todistaa.
-
Johda luentomuistiinpanojen s. 11.6 esitetty, simuloidun jäähdytyksen
asymptoottista konvergenssia kun koskeva Seurauslause 2
samalla sivulla esitetystä, algoritmin käyttäytymistä vakiolämpötilassa
T > 0 koskevasta Lauseesta 1.
-
Hahmottele simuloitua jäähdytystä käyttävä ratkaisumenetelmä MAX
CLIQUE -optimointiongelmalle. Valitse sopiva kustannusfunktio
ja naapurustorakenne. Varmista, että osaat tuottaa annetun kelvollisen
ratkaisun satunnaisia naapuriratkaisuja tasaisen jakauman mukaan.
Minkälaista jäähdytysaikataulua ongelman ratkaisemiseen n solmun
verkossa tulisi käyttää luennolla esitetyn konvergenssilauseen 3
(luentomuistiinpanojen s. 11.11) mukaan?
Pekka Orponen
Fri Apr 14 16:17:21 EET DST 2000