A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows
(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:
https://lup.lub.lu.se/record/7424973
- author
- Lingas, Andrzej LU and Persson, Mia
- organization
- publishing date
- 2015
- 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
- 2016-04-01 10:20:50
- date last changed
- 2022-04-12 05:26:54
@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}},
keywords = {{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}},
doi = {{10.1007/s00453-013-9865-1}},
volume = {{72}},
year = {{2015}},
}