On Crossing Minimization Problems: Complexity and a Heuristic Approach

Abstract

In deze scriptie wordt een een heuristieke aanpak van een one-sided crossings minimization problem (OCMP) voor de PACE challenge 2024 besproken (https://pacechallenge.org/2024/). Een OCMP is, kort gezegd, een optimaliseringsprobleem bedoelt om een hiërarchische graaf te ordenen zodanig dat het aantal kruisingen tussen zijdes, minimaal is. We bespreken eerst varianten van crossings problems in het algemeen, en daarna leggen we de focus op OCMP, waarvan we weten dat het NP-compleet is. Dan bespreken we bekende (heuristieke) methodes, met een korte vergelijking, en onze motivatie m.b.t. de gekozen methodes voor de implementatie voor PACE. Vervolgens bespreken we ons programma voor de heuristieke track van de PACE challenge in detail. Afsluitend nog kort een discussie en vooruitblik op verdere mogelijkheden, zowel voor het geïmplementeerde programma, als qua theorie.