Tietojenkäsittelyteoria, kevät 2000
Harjoitus 13, to 20.4. klo 10-12 sali MaD381

1. 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.
2. 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.
3. 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?