On the Complexity and Approximability of Budget-Constrained Minimum
Cost Flows✩
Michael Holzhausera,∗, Sven O. Krumkea , Clemens Thielena

arXiv:1607.02282v1 [cs.DS] 8 Jul 2016

a

University of Kaiserslautern, Department of Mathematics
Paul-Ehrlich-Str. 14, D-67663 Kaiserslautern, Germany

Abstract
We investigate the complexity and approximability of the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a second kind of costs
associated with each edge, whose total value in a feasible flow is constrained by a given budget B.
This problem can, e.g., be seen as the application of the ε-constraint method to the bicriteria minimum cost flow problem. We show that we can solve the problem exactly in weakly polynomial
time O(log M · MCF(m, n, C, U)), where C, U, and M are upper bounds on the largest absolute cost,
largest capacity, and largest absolute value of any number occuring in the input, respectively, and
MCF(m, n, C, U) denotes the complexity of finding a traditional minimum cost flow. Moreover, we
present two fully polynomial-time approximation schemes for the problem on general graphs and one
with an improved running-time for the problem on acyclic graphs.
Keywords: algorithms, complexity, minimum cost flow, approximation
1. Introduction
In this paper, we investigate the natural extension of the traditional minimum cost flow problem
(cf., e.g., [1]) by a second kind of costs, called usage fees, which are linear in the flow on the corresponding edge and bounded by a given budget B.
This extension allows us to solve many related
problems such as the budget-constrained maximum dynamic flow problem (since each dynamic
✩

This work was partially supported by the German Federal Ministry of Education and Research within the project
“SinOptiKom – Cross-sectoral Optimization of Transformation Processes in Municipal Infrastructures in Rural Areas”.
∗
Corresponding author. Fax: +49 (631) 205-4737.
Phone: +49 (631) 205-2511
Email addresses:
holzhauser@mathematik.uni-kl.de (Michael
Holzhauser), krumke@mathematik.uni-kl.de (Sven O.
Krumke), thielen@mathematik.uni-kl.de (Clemens
Thielen)

flow can be represented as a traditional minimum
cost flow (cf. [2])) or the application of the εconstraint method to the bicriteria minimum cost
flow problem (cf., e.g., [3]).
To the best of our knowledge, the budgetconstrained minimum cost flow problem was first
mentioned in [1], where a structural result but
no combinatorial algorithm was presented. A related problem in which a fixed usage fee is induced by each edge with positive flow was investigated by Duque et al. [4]. The model that we
use here was recently investigated in Holzhauser
et al. [5], where a strongly polynomial-time algorithm based on the interpretation of the problem
as a bicriteria minimum cost flow problem was
derived.
We extend these results and show that, using similar ideas, we can also obtain a weakly
polynomial-time combinatorial algorithm that
performs worse only by a logarithmic factor
than the best algorithm for the traditional min-

imum cost flow problem. Moreover, we present
two fully polynomial-time approximation schemes
(FPTAS), one of which is based on techniques
introduced by Papadimitriou and Yannakakis [6]
and has a weakly polynomial running-time and
one of which is based on the packing-LP framework developed by Garg and Koenemann [7],
achieving a strongly-polynomial running-time.
The running-time of the latter FPTAS is subsequently improved for the case of acyclic graphs.

BCMCFPR is always non-positive. The problem
is a generalization of the problem variant in which
a desired flow value F is given since we can “enforce” such a flow value by adding an edge with
negative costs of large absolute value and capacity F (cf. [5] for further details).
2.2. Approximation Algorithms
An algorithm A is called a (polynomial-time)
approximation algorithm with performance guarantee α ∈ [1, ∞) or simply an α–approximation
for BCMCFPR if, for each instance I of
BCMCFPR with optimum solution x∗ , it computes a feasible solution x with objective value
c(x) ≤ α1 c(x∗ ) in polynomial time (note that c(x)
and c(x∗ ) are non-positive, so α1 c(x∗ ) ≥ c(x∗ )).
An algorithm A that receives as input an instance I ∈ Π and a real number ε ∈ (0, 1) is called
a polynomial-time approximation scheme (PTAS)
if, on input (I, ε), it computes a feasible solution x
with objective value c(x) ≤ (1 − ε) · c(x∗ ) with a
running-time that is polynomial in the encoding
size |I| of I. If this running-time is additionally
polynomial in 1ε , the algorithm is called a fully
polynomial-time approximation scheme (FPTAS).
Moreover, for the case of BCMCFPR , we call
an algorithm a bicriteria FPTAS if, for each ε ∈
(0, 1), it computes a solution x with c(x) ≤ (1 −
ε) · c(x∗ ) and b(x) ≤ (1 + ε) · b(x∗ ) in polynomial
time.

2. Preliminaries
2.1. Problem Definition
In the budget-constrained minimum cost flow
problem (abbreviated as BCMCFPR in the following), we are given a directed multigraph G =
(V, E) with edge capacities ue ∈ N≥0 , costs ce ∈ Z
(i.e., we allow integral costs with arbitrary sign),
and usage fees be ∈ N≥0 per unit of flow on the
edges e ∈ E, as well as a budget B ∈ N≥0
and a distinguished source s ∈ V and sink t ∈
V . The aim is to P
find a feasible s-t-flow x in
G that minimizesP e∈E ce · xe subject to the
budget-constraint e∈E be · xe ≤ B. The problem BCMCFPR can be stated as a linear program as follows:
X
min
ce · xe
(1a)
e∈E

s.t.

X

xe −

e∈δ− (v)

X

X

xe = 0 ∀v ∈ V \ {s, t},

e∈δ+ (v)

be · xe ≤ B,

(1b)

2.3. Parametric Search

(1c)

Throughout the paper, we make use of
Megiddo’s parametric search technique (cf. [8]),
which can be described as follows: Assume that
we want to solve an optimization problem Π for
which we already know an (exact) algorithm A
that solves the problem, but in which some of
the input values are now linear parametric values
that depend linearly on some real parameter λ.
Moreover, suppose that an algorithm C is known
(in the following called callback ) that is able to
decide if some candidate value for λ is smaller,
larger, or equal to the value λ∗ that leads to an
optimum solution to the underlying problem Π.
The idea of the parametric search technique is to

e∈E

0 ≤ xe ≤ ue

∀e ∈ E.

(1d)

Here, we denote by δ + (v) (δ − (v)) the set of outgoing (incoming) edges of some node v ∈ V . We
assume that there are no nodes v ∈ V \{s, t} with
δ + (v) = ∅ or δ − (v) = ∅ since no flow can reach
such nodes due to flow conservation. Note that
we can detect and remove such nodes along with
their incident edges in linear time.
Furthermore, note that since the zero-flow is
always feasible and has objective value zero,
the optimal objective value of each instance of
2

problem with the two objective functions c(x)
and b(x) that minimizes c(x) while maintaining
b(x) ≤ B. Graphically, each optimum solution x∗
of BCMCFPR corresponds to a point in the objective space that lies on the pareto frontier and
not above the line b = B.1 The situation is shown
in Figure 1.

simulate the execution of algorithm A with variables that still depend on the symbolic value λ,
and to continue the execution until we reach a
comparison of two linear parametric values that
needs to be resolved. Since both values depend
linearly on λ, it either holds that one of the variables is always larger than or equal to the other
one (in which case the result of the comparison
is independent from λ) or that there is a unique
intersection point λ′ . For this intersection point,
we evaluate the callback C in order to determine
if λ′ < λ∗ , λ′ > λ∗ , or λ′ = λ∗ and, thus, resolve the comparison and continue the execution.
Hence, as soon as the simulation of A finishes, we
have obtained an optimum solution to Π. The
overall running-time is given by the running-time
of A times the running-time of C and can be further improved using parallelization techniques described in [9]. We refer to [8] for further details on
the parametric search technique. Further applications and extenions of parametric search techniques can moreover be found in [10, 11, 12].

b

(c(x∗ ), b(x∗ ))T

b=B

0

c

Figure 1: The objective space of the interpretation of
BCMCFPR as a bicriteria minimum cost flow problem.
The gray area corresponds to the set of the objective values of feasible flows, the thick black lines correspond to
efficient edges, which form the pareto frontier.

3. Exact Algorithms
We start with results on the complexity of the
problem BCMCFPR . The mathematical model
(1a) – (1c) for BCMCFPR , as introduced in
Section 2, is a linear program, which can be
solved in weakly polynomial time by known techniques such as interior point methods (cf. [13]).
In particular, using the procedure described by
Vaidya [14] to our multigraph setting, we get
the following weakly polynomial running-time for
BCMCFPR :

It is well-known that, for each point (c, b)T on
the pareto frontier, there is some value λ ∈ [0, ∞)
and a feasible flow x with (c(x), b(x))T = (c, b)T
such that x is a minimum cost flow with respect
to the costs be + λ · ce for each edge e ∈ E (cf. Geoffrion [16]). Assume that there are two flows x1
and x2 that are both optimal for some specific
value of λ, i.e., b(x1 )+λ·c(x1 ) = b(x2 )+λ·c(x2 ) =
α for some value α. Then, for both of the flows xi
with i ∈ {1, 2}, it holds that b(xi ) = α − λ · c(xi ),
i.e., they lie on the same efficient edge, which is a
straight line with slope −λ in the objective space.
In other words, computing a minimum cost flow
with edge-costs be + λ · ce will either provide a solution that corresponds to on an extreme point of
the pareto frontier or some point that lies on the
efficient edge with slope −λ. Moreover, as shown

Theorem 1. BCMCFPR is solvable in weakly
polynomial time O(m2.5 · log M).

However, in this paper, we are interested in
combinatorial algorithms that exploit the structure of the underlying problem. We show how
we can incorporate combinatorial algorithms for
the traditional minimum cost flow problem in order to solve the more general budget-constrained
minimum cost flow problem BCMCFPR .
We can solve BCMCFPR by computing an efficient solution of the bicriteria minimum cost flow

1

We refer to [15] for an in-depth treatment of bicriteria
optimization problems and efficient solutions.

3

in [5], the slopes of these efficient edges differ by
minimum absolute amounts:

We now show how we can use Lemma 2 within
a binary search in order to obtain a weakly
polynomial-time algorithm that performs within
a factor O(log M) of each algorithm for the traditional minimum cost flow problem:

Lemma 1 ([5]). The slopes of two efficient
edges on the pareto frontier of any instance of
BCMCFPP
R differ by an absolute value of at least
1

for c := e∈E |ue · ce |.
c2

Theorem 3. BCMCFPR is solvable in weakly
polynomial time O(log M · MCF(m, n, C, U)).

As explained above, each optimum solution x∗
of BCMCFPR is a minimum cost flow with respect to the edge-costs ce + λ∗ · be for at least one
value λ∗ ∈ [0, +∞). In particular, if Λ∗ denotes
the set of all these values λ∗ , it holds that Λ∗ is a
closed interval containing either one or infinitely
many such values λ∗ depending on whether the
optimum solutions correspond to points that lie
amid or at the corner of some efficient edge in the
objective space, respectively. As claimed in the
following lemma, which is proven in [5], we are
able to decide the membership in Λ∗ efficiently:

:=
Proof.
Consider
the
set
K

1
2
where
k · 2c2 : k ∈ {0, . . . , b · 2c } ,
P
2
b := P e∈E ue · be ∈ O(m · M ) and
2
c :=
e∈E |ue · ce | ∈ O(m · M ) are upper
bounds on the total usage fees and total absolute
value of the costs of any feasible flow, respectively. Note that each extreme point of the pareto
frontier can be obtained by a minimum cost flow
computation with edge-costs ce + λ · be for some
λ ∈ K since the slopes of any two efficient
edges differ by an absolute amount of at least c12
according to Lemma 1. Hence, by incorporating
the procedure that is described in Lemma 2
into a binary search on the set K, we either
find some value λ ∈ Λ∗ (in which case we have
also found an optimum solution to BCMCFPR )
or two “adjacent” values λ(1) := k · 2c12 and
λ(2) := (k + 1) · 2c12 for some k ∈ {0, . . . , b · 2c2 − 1}
with λ(1) < min Λ∗ and λ(2) > max Λ∗ . These
values, however, yield solutions x(1) and x(2)
that correspond to the corner points of the same
efficient edge, which crosses the line b = B
in the objective space. Thus, by computing a
suitable convex combination of the two solutions
x(1) and x(2) , we obtain an optimum solution to
BCMCFPR and are done.
The running-time of the procedure is dominated by the binary search on the set K and
the resulting O(log |K|) calls to the procedure
that is described in Lemma 2. Hence, the overall
running-time is given by

Lemma 2 ([5]). Let Λ∗ 6= ∅ denote the set of parameters λ∗ for which an optimum solution x∗ to
BCMCFPR is a minimum cost flow with respect
to the edge-costs ce + λ∗ · be for each e ∈ E. For
some candidate value λ, it is possible to decide
whether λ < min Λ∗ , λ > max Λ∗ , or λ ∈ Λ∗ in
O(MCF(m, n, C, U)) time.

Let MCF(m, n) denote the complexity of computing a traditional minimum-cost flow in strongly
polynomial time. As shown in [5], Lemma 2 can
be used within Megiddo’s parametric search technique in order to obtain strongly polynomial-time
algorithms for BCMCFPR :
Theorem 2 ([5]). BCMCFPR
is
solvable
in strongly polynomial time O(m log m ·
min{T1 (m, n), T2 (m, n), T3 (m, n)}) with
• T1 (m, n) ∈ O((m + n log n) · MCF(m, n)),

O(log |K| · MCF(m, n, C, U))
= O(log(b · c2 ) · MCF(m, n, C, U))
= O(log(m3 · M 6 ) · MCF(m, n, C, U))
= O(log M · MCF(m, n, C, U)),

• T2 (m, n) ∈ O((n · log m
+ n · log n + log m) ·
n
MCF(m, n) + m), and
• T3 (m, n) ∈ O(log log m·log2 m·MCF(m, n)+
f (m)) for f (m) ∈ o(m3 ).


which shows the claim.
4



4. Approximation Algorithms

We now show how we can obtain an FPTAS with strongly polynomial running-time using a different approach based on a combination
of Garg and Koenemann’s packing-LP framework
and Megiddo’s parametric search technique. We
will therefore need the following auxiliary lemma:

4.1. General Graphs
In [6], the authors show that an ε-approximate
pareto frontier (i.e., a set of points Pε such that,
for each point y on the pareto frontier P , there
is a point y ′ ∈ Pε such that y is within a
factor of (1 + ε) from y ′ in each component)
of a linear convex optimization problem with
k objective functions can be determined by solving O((8Lk 2 /ε)k ) instances of the problem with
only one objective function, where L denotes the
encoding-length of the largest possible objective
value. Applied to BCMCFPR , we are, thus, able
to determine
an ε-approximatepareto frontier


log M 2
in O
· MCF(m, n, C, U) time, which in
ε
turn implies a bicriteria FPTAS for BCMCFPR .
The following lemma shows that this also yields a
traditional FPTAS for BCMCFPR :

Lemma 4. Let λ be a parameter with a callback
that fulfills C(m, n) ∈ Ω( logmm ). Any multigraph G
with linear parametric edge-lengths le (λ) on each
e ∈ E can be turned into a simple graph G′ that
only contains the shortest edge among all parallel
edges between two nodes in O(log m · log log m ·
C(m, n)) time.
Proof. Let S := {(v, w) ∈ V 2 : |δ + (v) ∩
δ − (w)| ≥ 2} denote the set of all pairs of nodes
with at least two parallel edges between them.
In order to determine the simple graph G′ with
the desired properties, we need to evaluate the
minimum of all edges in δ + (v) ∩ δ − (w) for each
(v, w) ∈ S. As shown in [17], we can determine
the minimum of k values in O(log log k) time using O(k) processors. We simulate all of these computations P
in parallel, which results in a total number of O( (v,w)∈S |δ + (v) ∩ δ − (w)|) = O(m) processors. In order to reduce the number of callback calls, we simulate the O(m) processors sequentially in a round-robin manner until each of
them either finishes its computation or holds at
the comparison of two linear parametric values,
yielding O(m) candidate values for λ that need
to be resolved using the callback for λ. Using a
binary search on the set of these candidate values in combination with a successive determination of the median, which can be employed in
O(m) time according to Blum et al. [18], we can
resolve all of the comparisons simultaneously in
O(log m·C(m, n)+m) time and continue the simulation of the processors. After O(log log m) iterations of the above procedure, each processor has
finished its computation and the edge with minimum length is determined for each (v, w) ∈ S,
which shows the claim.


Lemma 3. Any
bicriteria
FPTAS
for
BCMCFPR also induces a single-criterion
FPTAS for BCMCFPR .
Proof. For each instance of BCMCFPR with
optimum solution x∗ , the given bicriteria FPTAS
computes a solution x with c(x) ≤ (1 − ε) · c(x∗ )
and b(x) ≤ (1 + ε) · b(x∗ ) in time that is polynomial in the instance size and 1ε . Since both the
costs c and usage fees b are linear functions, it suffices to scale down the given solution as follows:
x
Let x′ := 1+ε
. Clearly, x′ is feasible since it still
fulfills every flow conservation and capacity con1
straint and since b(x′ ) = 1+ε
· b(x) ≤ b(x∗ ) ≤ B.
Moreover, for ε′ := 2ε, it holds that
1−ε
1
· c(x) ≤
· c(x∗ )
1+ε
1+ε
′ 2
ε′
1− 2
1 − ε′ + (ε4)
∗
· c(x∗ )
=
′ · c(x ) =
(ε′ )2
1 + ε2
1− 4

c(x′ ) =

≤ (1 − ε′ ) · c(x∗ ),
which shows the claim.



Corollary 1. There
is
an
FPTAS
for
BCMCFPR that
runs
in


log M 2
O
· MCF(m, n, C, U) time.

ε

5

Theorem 4. There
is
an
FPTAS
for
BCMCFPR that runs in strongly
polynomial2
1
2
3
e
time O ε2 · (m · n + m · n ) .

Note that, since c(C) < 0 for each C ∈ C, we
can rewrite equation (2) as
P
b(C) · µ + e∈C ye
≥ 1,
−c(C)

Proof. We consider an equivalent, circulationbased version of BCMCFPR that can be obtained
by inserting an edge with infinite capacity, zero
costs, and zero usage fees between t and s. Then,
according to the flow decomposition theorem for
traditional flows (cf. [1]), each optimum flow x∗
is positive on O(m) simple
P cycles C with strictly
negative costs c(C) := e∈C ce < 0. Let C denote the set of all such simple cycles with P
negative
costs the underlying graph. For b(C) := e∈C be ,
we obtain the following cycle-based formulation
of BCMCFPR :
X
min
c(C) · xC

or, equivalently,
P

X

xC ≤ ue

X

b(C) · xC ≤ B,

∀e ∈ E,

C∈C:

e∈C

C∈C

xC ≥ 0

∀C ∈ C.

The dual of this linear program can be stated as
follows:
min B · µ +

X

ue · ye ,

A(m, n) = O(m · n · log m log log m

e∈E

s.t. b(C) · µ +

X

ye ≥ −c(C)

P

Hence, we are done if we can determine the minimum ratio cycle C ∈ C with edge-costs be ·
µ + ye and edge-times −ce in polynomial time.
Megiddo [9] derived an algorithm that determines
the minimum ratio cycle in a simple graph in
O(n3 log n + m · n log2 n log log n) time by computing all-pair shortest paths in combination with
Karp’s minimum mean cycle algorithm [19] as a
callback function in his parametric search. In order to comply with our setting of multigraphs,
we first need to apply Lemma 4 with the minimum mean cycle algorithm as a callback, running in C(m, n) := O(m · n) time, to the underlying graph, which yields a running-time of
O(m · n · log m · log log m). In total, we get that

C∈C

s.t.

· µ + ye )
≥ 1.
e∈C −ce

e∈C (be

∀C ∈ C,

+ n3 log n + m · n · log2 n log log n).

(2)

e∈C

ye ≥ 0
µ ≥ 0.

Thus, incorporated in Garg and Koenemann’s
framework, we obtain an overall running-time of


1
O 2 · m log m · A(m, n)
ε


1
2
3
e
· (m · n + m · n ) .
=O
ε2

∀e ∈ E,

Although the number of variables (constraints) is
exponential in the primal (dual), we are able to
derive a strongly polynomial-time FPTAS for the
problem using the packing-LP framework introduced by Garg and Koenemann [7]. In short,
Garg and Koenemann show that, as long as it
is possible to determine the most-violated constraint of the dual for some infeasible dual solution (y, µ) with y > 0 and µ > 0 in polynomial
time O(A(m, n)), then there is an FPTAS with a
running-time in O( ε12 · m log m · A(m, n)).
e
To simplify running-times, it is common to use O(p)
k
in order to denote O(p · log m) with k ∈ O(1).



4.2. Acyclic Graphs
We now show how we can improve the runningtime of the FPTAS described in Theorem 4 for
the case of an acyclic graph G. Since there are
no cycles in G, we only need to repeatedly determine minimum ratio s-t-paths rather than minimum ratio cycles. This, however, can be done
more efficiently, as shown in the following lemma:

2

6

Lemma 5. Let d(1) : E → R and d(2) : E → R
(1)
be two cost functions with de := d(1) (e) and
(2)
de := d(2) (e) for each e ∈ E and assume that
P
(2)
∗
e∈P de > 0 for each s-t-path P . An s-t-path P
that minimizes the ratio

P

(1)

e∈P

de

e∈P

de

P

computations at an overhead of O(|δ + (v)|) for the
median computations. This results in an runningtime for the parametric shortest path computation of


X
O
(log |δ + (v)| · m + |δ + (v)|)

(2)

among all s-t-

paths P can be found in O(m · (log m log log m +
n · log n)) time on acyclic graphs.

v∈V \{t}

= O (m · n · log n) ,

Proof. Let P denote the set of all s-t-paths
in the underlying acyclic graph G. Similar
to Megiddo [8] and Chandrasekaran [20], we
can restrict
considerations to the problem
P our
(1)
(2)
(λ)
(λ)
minP ∈P e∈P de with de := de − λ · de
for each e ∈ E and some parameter λ: Using similar arguments as in [20], it is easy to
see that, for some
value of λ, it holds
P candidate
(λ)
that minP ∈P e∈P de is negative (positive) if
and only if the value of λ is smaller (larger) than
the value λ∗ that leads to an optimum solution P ∗
to minP ∈P

P

By incorporating the results of Lemma 5 in the
packing-LP framework of Garg and Koenemann
as described in the proof of Theorem 4, we immediately get the following corollary:
Corollary 2. There
is
an
FPTAS
for
BCMCFPR
that
runs in
O ε12 · m2 log m · (log m log log m + n log n)
time on acyclic graphs.


(1)

e∈P

de

e∈P

de

P

which in, combination with the overhead of O(m ·
log m·log log m) for the transformation into a simple graph, shows the claim.


(2)

.

Hence, by simulating the

shortest path algorithm for acyclic graphs with
edge lengths d(λ) for a symbolic value of λ using Megiddo’s parametric search technique, it is
possible to determine the optimum solution P ∗ in
O(m2 ) time.
We can improve this running-time by first
applying Lemma 4 to the underlying multigraph in order to obtain a simple graph with
the same shortest paths as in G in O(m ·
log m log log m) time. In this simple graph, we
simulate the shortest path algorithm for acyclic
graphs, which initially sets the distance label of
each node to infinity. It then investigates the
nodes in the order of a topological sorting and, for
each outgoing edge e = (v, w) of some node v ∈
V \ {t} in this sorting, updates the distance label dist(w) of node w to min{dist(w), dist(v)+le}
where le denotes the length of edge e, which results in a comparison of two linear parametric values. Note that the edges in δ + (v) head to different
nodes since the underlying graph is simple, so all
of these comparisons are independent from each
other. Thus, by evaluating a binary search over
the set of candidate values that result from each of
these comparisons as described in [9] and as used
above, we only need O(log |δ + (v)|) shortest path

5. Conclusion
In this paper, we presented results on the
complexity and approximability of the budgetconstrained minimum cost flow problem. As
the problem is known to be solvable both
in weakly polynomial time by interior-point
methods and in strongly-polynomial time as
shown in [5], we developed a new combinatorial algorithm that runs in weakly polynomial time O(log M · MCF(m, n, C, U)). Moreover, we presented a weakly polynomial-time FPTAS that uses the ε-approximate pareto frontier
and a strongly polynomial-time FPTAS based on
both Garg and Koenemann’s packing-LP framework and Megiddo’s parametric search technique.
Moreover, we could show that we can improve the
running-time of the latter algorithm for the case
of acyclic graphs.
References
[1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network
Flows, Prentice Hall, 1993.

7

[2] L. R. Ford, D. R. Fulkerson, Constructing Maximal
Dynamic Flows from Static Flows, Operations Research 6 (1958) 419–433.
[3] V. Chankong, Y. Y. Haimes, Multiobjective Decision
Making: Theory and Methodology, Dover Books on
Engineering Series, Dover Publications, Incorporated,
2008.
[4] P. A. M. Duque, S. Coene, P. G. K., Sörensen,
F. Spieksma, The accessibility arc upgrading problem, European Journal of Operational Research
224 (3) (2013) 458–465.
[5] M. Holzhauser, S. O. Krumke, C. Thielen, BudgetConstrained Minimum Cost Flows, Journal of Combinatorial Optimization 31 (4) (2016) 1720–1745.
[6] C. H. Papadimitriou, M. Yannakakis, On the approximability of trade-offs and optimal access of web
sources, in: Foundations of Computer Science, 2000.
Proceedings. 41st Annual Symposium on, IEEE, 86–
92, 2000.
[7] N. Garg, J. Koenemann, Faster and simpler algorithms for multicommodity flow and other fractional packing problems, SIAM Journal on Computing 37 (2) (2007) 630–652.
[8] N. Megiddo, Combinatorial optimization with rational objective functions, Mathematics of Operations
Research 4 (4) (1979) 414–424.
[9] N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, Journal of
the ACM (JACM) 30 (4) (1983) 852–865.
[10] E. Cohen, N. Megiddo, Maximizing concave functions
in fixed dimension, World Scientific, 1990.
[11] S. Toledo, Approximate parametric searching, Information processing letters 47 (1) (1993) 1–4.
[12] S. Toledo, Maximizing non-linear concave functions
in fixed dimension, in: Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium
on, IEEE, 676–685, 1992.
[13] A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1998.
[14] P. M. Vaidya, Speeding-up linear programming using
fast matrix multiplication, in: Foundations of Computer Science, 1989., 30th Annual Symposium on,
IEEE, 332–337, 1989.
[15] M. Ehrgott, Multicriteria optimization, Springer, 2nd
edn., 2005.
[16] A. M. Geoffrion, Solving bicriterion mathematical
programs, Operations Research 15 (1) (1967) 39–54.
[17] L. G. Valiant, Parallelism in comparison problems,
SIAM Journal on Computing 4 (3) (1975) 348–355.
[18] M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E.
Tarjan, Linear time bounds for median computations,
in: Proceedings of the fourth annual ACM symposium on Theory of computing, ACM, 119–124, 1972.
[19] R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete mathematics 23 (3)
(1978) 309–311.

[20] R. Chandrasekaran, Minimal ratio spanning trees,
Networks 7 (4) (1977) 335–342.

8

