Search

This paper shows a graph partition problem polynomially solvable. Moreover, the problem in the planar case leads to a number of problems in graphs and combinatorial optimizations polynomially solvable.

Researchers in the area of electoral systems have recently turned their attention to network flow techniques with the aim to resolve certain practically relevant problems arising in this area. The aim of this paper is to review some of this work, showing the applicability of these techniques even to problems of a very different nature. Major emphasis will be placed on “biproportional apportionment,” a problem that frequently arises in proportional electoral systems, but which in some countries is still ill-solved, or not dealt with rigorously, notwithstanding the availability of several sound solution procedures and their concrete application in some real-life elections. Besides biproportional apportionment, we shall discuss applications of network flows to problems such as vote transitions and political districting. Finally, we address the so-called “give-up problem,” which arises in the current elections for the Italian Parliament. It is related to the possible assignment of seats to multiple winners of a given party. Based on the results and techniques presented in this article, it is fair to state that network flow models and algorithms are indeed very flexible and effective tools for the analysis and the design of contemporary electoral systems. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

ABBaziE is a freely available Java-program to convert a Bazi output file into an Excel worksheet, and vice versa. Bazi output files come in plain ASCII text format. ABBaziE interprets their structure, and generates an appropriate file in Excel format. ABBaziE ist ein frei verfügbares Java-Programm, um eine Bazi-Ausgabedatei in ein Excel-Arbeitsblatt zu konvertieren und umgekehrt. Bazi-Dateien haben einfaches ASCII Textformat. ABBaziE interpretiert deren Struktur und erzeugt eine entsprechende Excel-Datei.

A new analysis of the Iterative Proportional Fitting procedure is presented. The input data consist of a nonnegative matrix, and of row and column marginals. The output sought is a biproportional fit, that is, a scaling of the input matrix by means of row and column divisors so that the scaled matrix has row and column sums equal to the input marginals. The IPF procedure is an algorithm alternating between the fitting of rows and columns. The structure of its accumulation points is explored in detail. The progress of the algorithm is evaluated through an L1-error function measuring the deviation of current row and column sums from target marginals. A formula is obtained, of max-flow min-cut type, to calculate the minimum L1-error directly from the input data. If the minimum L1-error is zero, the IPF procedure converges to the unique biproportional fit. Otherwise, it eventually oscillates between various accumulation points.

This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit-center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP-hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time.