Advanced

A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows

Lingas, Andrzej LU and Persson, Mia (2015) In Algorithmica 72(2). p.607-619
Abstract
We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC... (More)
We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Maximum integral flow, Minimum-cost flow, Polynomial verification, Parallel algorithms, Randomized algorithms, Time complexity, Processor, complexity
in
Algorithmica
volume
72
issue
2
pages
607 - 619
publisher
Springer
external identifiers
  • wos:000354066300011
  • scopus:84929061709
ISSN
0178-4617
DOI
10.1007/s00453-013-9865-1
language
English
LU publication?
yes
id
6e9dc9d2-b7b0-4af7-b3da-74273babb135 (old id 7424973)
date added to LUP
2015-06-26 07:16:37
date last changed
2017-09-24 03:10:53
@article{6e9dc9d2-b7b0-4af7-b3da-74273babb135,
  abstract     = {We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.},
  author       = {Lingas, Andrzej and Persson, Mia},
  issn         = {0178-4617},
  keyword      = {Maximum integral flow,Minimum-cost flow,Polynomial verification,Parallel algorithms,Randomized algorithms,Time complexity,Processor,complexity},
  language     = {eng},
  number       = {2},
  pages        = {607--619},
  publisher    = {Springer},
  series       = {Algorithmica},
  title        = {A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows},
  url          = {http://dx.doi.org/10.1007/s00453-013-9865-1},
  volume       = {72},
  year         = {2015},
}