« Projekte
Sie verwenden einen sehr veralteten Browser und können Funktionen dieser Seite nur sehr eingeschränkt nutzen. Bitte aktualisieren Sie Ihren Browser. http://www.browser-update.org/de/update.html
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 ...