Leírás
Az optimális pártos választókerület-szabdalás egy párt számára a nyerő
választókerületek számát maximalizáló szabdalás. Korábbi munkáinkban
(Puppe és Tasnádi, 2009, illetve Fleiner, Nagy és Tasnádi, 2017) különböző
modellkereteket alapul véve, igazoltuk az optimális pártos választókerület-szabdalás
NP-teljességét. Megvizsgáljuk, hogy az alkalmazott redukciók approximációt
megőrzők-e, továbbá az irodalomban található újabb eredményekre is kitérünk. Egyfajta
közelítő algoritmus kiindulópontja a "crack and pack" eljárás, amely segítségével
könnyen illusztrálható, hogy egy párt maga számára előnyösen szabdalhatja a
választókerületeket. Az eljárás lényege, hogy a szabdalást végrehajtó párt
minimális szavazatokkal nyerő választókerületeket hoz létre, míg más
választókerületekben a rivális párt támogatóit tömbösíti. Megvizsgáljuk a "crack and
pack" eljárás közelítési tulajdonságát és a modellkerettől függő hatékonyságát.