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


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









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

Abstract, Links, ©

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},
}


Entry last modified by Christine Kiesel, 06/19/2006
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Dimitrios Michail
Created
03/09/2005 05:30:13 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Tamara Hausmann
Dimitrios Michail
Dimitrios Michail
Edit Dates
19.06.2006 10:13:09
13.06.2006 12:27:36
03/09/2005 05:33:32 PM
03/09/2005 05:30:13 PM