patternMinor
Minimum cost circulation problem with bounded number of edges
Viewed 0 times
problemnumberedgeswithminimumcirculationboundedcost
Problem
During an article I am writing, I encountered the following problem:
Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$.
Find a circulation $f$ with minimal cost $W(f)$ such that the number of edges used by the circulation (i.e., edges $e$ s.t. $f(e)> 0$) is smaller than or equal to a parameter $r$.
Note that if $r=|E|$, the problem is simply the well-known circulation, which is solvable in polynomial time.
I tried to search "Google Scholar" and use variations of the cycle canceling (and other min cost flow) algorithms to solve the problem but with no successes.
Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$.
Find a circulation $f$ with minimal cost $W(f)$ such that the number of edges used by the circulation (i.e., edges $e$ s.t. $f(e)> 0$) is smaller than or equal to a parameter $r$.
Note that if $r=|E|$, the problem is simply the well-known circulation, which is solvable in polynomial time.
I tried to search "Google Scholar" and use variations of the cycle canceling (and other min cost flow) algorithms to solve the problem but with no successes.
Solution
After I posted the question in cstheory, I received an answer there.
Your problem is NP-Hard and even hard to approximate via easy reductions from Steiner tree problem. Look at the following paper for more information. dl.acm.org/citation.cfm?doid=1077464.1077470.
Your problem is NP-Hard and even hard to approximate via easy reductions from Steiner tree problem. Look at the following paper for more information. dl.acm.org/citation.cfm?doid=1077464.1077470.
Context
StackExchange Computer Science Q#95479, answer score: 2
Revisions (0)
No revisions yet.