Network Problems with Non-Polynomial Weights And Applications

The most efficient algorithms for several network problems like minimum cost flow and the maximum weight matching problem follow the primal-dual paradigm. These algorithms perform arithmetic (additions and subtractions) on numbers of magnitude O(nC) when the edge weights (also called costs) are integers bounded by C and n denotes the number of vertices. Under the standard assumption that arithmetic on numbers of magnitude O(n) has constant cost, arithmetic on numbers of this size has cost O((log C)/ log n). We show for the scaling versions of these algorithms that arithmetic on numbers of size polynomial in n suffices without increasing the asymptotic number of arithmetic operations. In this way