Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem - Danish National Research Database-Den Danske Forskningsdatabase

^{1} Department of Mathematical Sciences, Faculty of Science, Aarhus University, Aarhus University^{2} University of Wuppertal^{3} Department of Mathematics, Science and Technology, Aarhus University^{4} Department of Mathematics, Science and Technology, Aarhus University

DOI:

10.1007/s10732-007-9065-8

Abstract:

The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.

Type:

Journal article

Language:

English

Published in:

Journal of Heuristics, 2009, Vol 15, Issue 4, p. 331-349

Keywords:

Fixed-charge transportation problem · Min-knapsack problem · Greedy Fixed-charge transportation problem, min-knapsack problem, greedy algorithms, worst-case analysis, approximation algorithms