Forschungsportal Sachsen-Anhalt
« Projekte

Biproportionale Rundungen

Finanzierung:
Haushalt;
Bei der Besetzung von Gremien soll oft eine Proportionalität hinsichtlich zweier Kategorien erfolgen, z.B. Parteien (proportional zu ihren Wahlergebnissen) und Regionen (proportional zur Einwohnerzahl). Die Sitze im Gremium können natürlich nur in ganzen Einheiten zugeordnet werden. Das führt zum Problem der biproportionalen (ganzzahligen) Rundung einer nicht-negativen Matrix. Kombinatorische Algorithmen sowie der sehr einfache BAZI-Algorihmus sollen untersucht und verglichen werden. Eine guter Ansatzpunkt ist eine Formulierung des Problems als ein ganzzahliges Optimierungsproblem, was in die Richtung der Minimierung einer konvexen (nicht-linearen) Kostenfunktion über einem Transportpolytop (evtl. mit Kapazitätsbeschränkungen) geht.

Schlagworte

Bipartiter Graph, Fenchel-Dualität, Fluss und Potential., Netzwerk

Kontakt

weitere Projekte

Die Daten werden geladen ...