A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

BECKER, Ruben, Maximilian FICKERT, Andreas KARRENBAUER, 2016. A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem. ALENEX16 : Meeting on Algorithm Engineering & Experiments. Arlington, Virginia, USA, 10. Jan 2016 - 10. Jan 2016. In: GOODRICH, Michael, ed., Michael MITZENMACHER, ed.. 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). ALENEX16 : Meeting on Algorithm Engineering & Experiments. Arlington, Virginia, USA, 10. Jan 2016 - 10. Jan 2016, pp. 151-159. ISBN 978-1-61197-431-7

@inproceedings{Becker2016Novel-34517, title={A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem}, year={2016}, doi={10.1137/1.9781611974317.13}, isbn={978-1-61197-431-7}, booktitle={2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX)}, pages={151--159}, editor={Goodrich, Michael and Mitzenmacher, Michael}, author={Becker, Ruben and Fickert, Maximilian and Karrenbauer, Andreas} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/34517"> <dc:language>eng</dc:language> <dc:creator>Becker, Ruben</dc:creator> <dc:creator>Fickert, Maximilian</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-06-24T06:55:38Z</dcterms:available> <dc:contributor>Becker, Ruben</dc:contributor> <dcterms:issued>2016</dcterms:issued> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/34517"/> <dc:contributor>Karrenbauer, Andreas</dc:contributor> <dc:contributor>Fickert, Maximilian</dc:contributor> <dcterms:abstract xml:lang="eng">We present a novel algorithm for the min-cost flow problem that is competitive with recent third-party implementations of well-known algorithms for this problem and even outperforms them on certain realistic instances. We formally prove correctness of our algorithm and show that the worst-case running time is in O(‖b‖1(m + n log n)) where b is the vector of demands. Combined with standard scaling techniques, this pseudo-polynomial bound can be made polynomial in a straightforward way. Furthermore, we evaluate our approach experimentally. Our empirical findings indeed suggest that the running time does not significantly depend on the costs and that a linear dependence on ‖b‖1 is overly pessimistic. Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611974317.13</dcterms:abstract> <dcterms:title>A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem</dcterms:title> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-06-24T06:55:38Z</dc:date> <dc:creator>Karrenbauer, Andreas</dc:creator> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto