Universität zu Köln

Konen, David ORCID: 0000-0003-1747-8791, Schmidt, Daniel and Spisla, Christiane (2022). Finding all minimum cost flows and a faster algorithm for the K best flow problem. Discret Appl. Math., 321. S. 333 - 350. AMSTERDAM: ELSEVIER. ISSN 1872-6771

Full text not available from this repository.

Abstract

This paper addresses the problem of determining all optimal integer solutions of a linear integer network flow problem, which we call the all optimal integer flow (AOF) problem. We derive an O(F (m + n) + mn + M) time algorithm to determine all F many optimal integer flows in a directed network with n nodes and m arcs, where M is the best time needed to find one minimum cost flow. We remark that stopping Hamacher's well-known method for the determination of the K best integer flows (Hamacher, 1995) at the first sub-optimal flow results in an algorithm with a running time of O(Fm(n log n + m) + M) for solving the AOF problem. Our improvement is essentially made possible by replacing the shortest path sub-problem with a more efficient way to determine a so-called proper zero cost cycle using a modified depth-first search technique. As a byproduct, our analysis yields an enhanced algorithm to determine the K best integer flows that runs in O(Kn(3) + M). Besides, we give lower and upper bounds for the number of all optimal integer and feasible integer solutions. Our bounds are based on the fact that any optimal solution can be obtained by an initial optimal tree solution plus a conical combination of incidence vectors of all induced cycles with bounded coefficients. (C) 2022 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Konen, David UNSPECIFIED orcid.org/0000-0003-1747-8791 UNSPECIFIED Schmidt, Daniel UNSPECIFIED UNSPECIFIED UNSPECIFIED Spisla, Christiane UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-667292
DOI:	10.1016/j.dam.2022.07.007
Journal or Publication Title:	Discret Appl. Math.
Volume:	321
Page Range:	S. 333 - 350
Date:	2022
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1872-6771
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/66729