Optimization Online


The Budgeted Minimum Cost Flow Problem with Unit Upgrading Cost

Christina Büsing(buesing***at***math2.rwth-aachen.de)
Sarah Kirchner(kirchner***at***or.rwth-aachen.de)
Arie M.C.A. Koster(koster***at***math2.rwth-aachen.de)
Annika Thome(thome***at***or.rwth-aachen.de)

Abstract: The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing to reduce the cost of at most K arcs. In this paper, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3-SAT we prove strong NP-completeness and inapproximability, even on directed acyclic graphs. On the positive side, we identify three polynomial solvable cases: on arborescences, on so-called tree-like graphs, and on instances with a constant number of sinks. Furthermore, we develop dynamic programs with pseudo-polynomial running time for the BMCF(K) problem on (directed) series-parallel graphs and (directed) graphs of bounded treewidth.

Keywords: Minimum cost ow, bilinear problem, budgeted optimization, complexity

Category 1: Combinatorial Optimization

Category 2: Network Optimization

Category 3: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 10/27/2015
Entry Accepted: 10/27/2015
Entry Last Modified: 10/27/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society