`Paper' over Benaderingsalgoritmen (BA)

Bij het college BA dient een `paper' geschreven te worden: dit onderdeel is echter alleen bestemd voor studenten die het college volgen in het kader van hun derdejaars programma, dus in het bijzonder in de studierichting Informatica en Management.
Masterstudenten doen de Onderzoeksopdracht (dus niet dit paper).

A: Inleiding

Bij het ontwerpen van software-oplossingen voor velerlei problemen, blijkt vaak dat exacte oplossing te bewerkelijk is voor voorkomende probleemgroottes. Het college Benaderingsalgoritmen behandelt de tegenwoordige inzichten om dergelijke problemen benaderd op te lossen, met algoritmen die mogelijk wel doenbaar zijn.
Bij het college hoort een (individuele) opdracht die er op gericht is om voor een bekend probleem uit de wereld van de discrete optimalisering uit te zoeken welke impact de ontwikkeling van benaderingsalgoritmen voor dit probleem gehad heeft. (Masterstudenten doen een andere opdracht.)

B: Keuze van `probleem'

Kies het te onderzoeken probleem uit de volgende collectie (u mag zelf met een eigen voorstel komen). Omdat de opdracht individueel moet zijn, volgt op college een nadere aanwijzing m.b.t. de keuze.
Maximum Knapsack ... ...
Maximum (Weighted) Satisfiability Minimum Traveling Salesperson Minimum Facility Location
Minimum Set Cover Minimum Euclidean Travelling Salesperson Maximum Clique
Minimum 0/1-Linear Programming (Minimum Makespan) Scheduling ...

Zie bijv ook de index van het Creszenzi-Kann compendium, voor verdere keuzen.

(Hier staat de gemaakte keuze van onderwerp per deelnemer.)

C: Opdracht

Schrijf een paper dat op begrijpelijke wijze weergeeft wat over de modellering en algoritmische oplosbaarheid van het door u gekozen probleem (en de eventuele varianten ervan) bekend is. Besteed aandacht aan vragen zoals: Het paper moet in het Nederlands geschreven worden en zoveel mogelijk zelfbevattend zijn, dwz. leesbaar zijn zonder specifieke kennis van de geraadpleegde literatuur.

De richtomvang is ongeveer 7-10 bladzijden (meer mag), exclusief de titelpagina, inhoudsopgave en literatuurlijst. Het paper mag in een van de volgende vormen worden ingeleverd: op papier (voorkeur), als Postscript file, of als PDF-file.

Inleverdatum 17 februari 2003 (zie werkrooster voor wijziging).

D: Toelichting