Unpublished, Draft, To Appear @UnPublished Unveröffentlicht, Entwurf

 Show entries of: this year (2021) | last year (2020) | two years ago (2019) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Mehlhorn, Kurt Michail, Dimitrios dblp dblp
 BibTeX citekey*: MM05a

 Title, Booktitle
 Title*: Network Problems with Non-Polynomial Weights and Applications

 Vol, No, pp., Year
 Month: January Year: 2005 Language: English Pages: 11

 Note: LaTeX Abstract: 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, we obtain an $O(T + \sqrt{n}m\log(nC))$ time and $O(S + m)$ space algorithm for the maximum weight matching problem on bipartite graphs where $T$ and $S$ are the time and space bound of an algorithm to sequentially enumerate the sets $\E_i$, $1 \le i \le \ceil{\log C}$, of all edges having a one in the $i$-th bit of their weight. The previously best algorithm had running time $O(\sqrt{n}m (\log(nC))^2/\log n)$. We obtain similar improvements for the capacitated transshipment problem with polynomially bounded demands. Some matching problems on bipartite graphs reduce to weighted matching problems with $C = n^{r}$, $r \leq m$. For these problems, we have $T = O( r \sqrt{n} m \log n )$ and $S = O( m )$ and hence our algorithm improves upon previous solutions by a factor $\Theta(r)$. Categories / Keywords: algorithms, matchings, bipartite graphs, rank-maximal HyperLinks / References / URLs: Personal Comments: File Upload: Download Access Level: Working Group

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@UNPUBLISHED{MM05a,
AUTHOR = {Mehlhorn, Kurt and Michail, Dimitrios},
TITLE = {Network Problems with Non-Polynomial Weights and Applications},
YEAR = {2005},
PAGES = {11},
MONTH = {January},
}