Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control.
We study combinatorial optimization problems in which a set of distributed agents must achieve a global objective using only local information. Papadimitriou and Yannakakis [Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 121--129] initiated the study of such problems in a framework where distributed decision-makers must generate feasible solutions to positive linear programs with information only about local constraints. We extend their model by allowing these distributed decision-makers to perform local communication to acquire information over time and then explore the tradeoff between the amount of communication and the quality of the solution to the linear program that the decision-makers can obtain.Our main result is a distributed algorithm that obtains a $(1 approximation to the optimal linear programming solution while using only a polylogarithmic number of rounds of local communication. This algorithm offers a significant improvement over the logarithmic approximation ratio previously obtained by Awerbuch and Azar [Proceedings of the 35th Annual IEEE Symposium on  Foundations of Computer Science, 1994, pp. 240--249] for this problem while providing a comparable running time. Our results apply directly to the application of network flow control, an application in which distributed routers must quickly choose how to allocate bandwidth to connections using only local information to achieve global objectives. The sequential version of our algorithm is faster and considerably simpler than the best known approximation algorithms capable of achieving a $(1 approximation ratio for positive linear programming.
Introduction
. Processors in a distributed environment must make decisions
based only on local data, thus fast distributed algorithms must often do without
global information about the system as a whole. This is exactly why computing many
target functions in distributed models quickly is provably hard [15]. However, quite
surprisingly, some of the most interesting global optimization problems can be very
closely approximated based only on local information and a modest amount of local
communication.
Our work is motivated by the application of developing flow control policies which
must achieve global objective functions. Flow control is the mechanism by which
routers of a network distribute the available network bandwidth across connections.
In our work, routing policies determine the routes in the network that connections
must use to transmit packets. The problem of regulating the rates at which the connections
may inject data along these fixed routes is the problem of flow control. This
connection-oriented, or rate-based, approach to flow control is a standard for routing
available bit rate tra#c in ATM networks [9] and is expected to become widely used
in packet-switched networks. In this approach, each router in the network must make
regulatory decisions based only on local information, which typically consists of the
current transmission rates of connections using the router. Most existing flow control
policies try to satisfy local objective functions such as max-min fairness [7, 1, 11].
However, there are many other practical scenarios in which global objective functions
# Department of Computer Science, Hebrew University, Jerusalem, Israel (yairb@cs.huji.ac.il).
Department of Computer Science, Boston University, Boston, MA (byers@cs.bu.edu).
# Department of Computer Science, Technion, Haifa, Israel (danny@cs.technion.ac.il).
Much of this work was completed while the authors were a#liated with the International Computer
Science Institute in Berkeley, California, and the University of California, Berkeley. Research supported
in part by NSF operating grants CCR-9304722 and NCR-9416101 and by a grant from the
US-Israel Binational Science Foundation. The work presented in this paper appeared in preliminary
form in [6] and in [10].
Y. BARTAL, J. W. BYERS AND D. RAZ
are the appropriate choice. For example, in a commercial intranetwork in which users
are paying for use of the network bandwidth (possibly at di#erent rates), the administrator
would want to use a flow control policy which maximizes total revenue.
We express such a flow control policy objective as a positive linear program, a linear
program in which all entries of the constraint matrix are non-negative. Complicating
the issue is the problem that routers must generate feasible solutions to this linear
program (LP) quickly, and based only on available information.
Motivated by this application and other related applications, Papadimitriou and
Yannakakis considered the problem of having distributed decision-makers assign values
to a set of variables in a linear program, where the agents have limited information
[18]. In one scenario they describe, each agent, acting in isolation, must set the value
of a single primal variable, knowing only the constraints a#ecting that variable in the
LP. In the context of flow control, where the objective is to maximize the total flow
through the network, this corresponds to a setting in which connections only know
how many other connections share each of the routers they intend to use. When
all edge capacities are 1, their "safe" algorithm sets each connection's flow to the
reciprocal of the maximum number of connections which share an edge with that
connection. It is not hard to see that the worst-case approximation ratio achieved by
the "safe" algorithm is #), where # is the maximum number of connections that
share an edge. They also prove that the "safe" algorithm achieves the best possible
worst-case ratio when agents may not communicate, leaving open the possibility that
much better ratios can be obtained when agents can interact.
We extend their model to allow computation to proceed in a sequence of rounds,
in each of which agents can communicate a fixed-size message to their immediate
neighbors, where agents are neighbors if and only if they share one or more constraints
in the LP. Our goal is to determine the number of rounds necessary to achieve a
approximation ratio to the optimum LP solution. Although we focus on the
application of flow control, this study could also be performed on a range of resource
allocation problems including those described in [18]. We note that similar models
for describing the interaction between connections and routers in both theoretical and
practical evaluations of flow control policies have been suggested in [3, 1, 5, 16].
Of course, a centralized administrator with complete information could solve the
problem exactly using one of the well known polynomial-time algorithms for linear
programming (see for example, [14]). But recently, much faster algorithms that produce
approximate solutions to positive linear programs to within a #) factor of
optimal have been designed. The sequential algorithm of Plotkin, Shmoys and Tardos
[19] repeatedly identifies a globally minimum weight path, and pushes more flow along
that path. More recently, faster approximation algorithms have been considered for
several related flow and bin-packing problems [8, 12] using this same principle of repeatedly
choosing a good flow, and incrementally increasing the rate of that flow. The
technical di#culty is to balance the amount of flow increase such that the required
approximation is achieved, with the number of needed steps (i.e. running time). In all
these algorithms a global operator of choosing the appropriate unsatisfied constraints
is used. Moreover, the more general multicommodity flow problem cannot be formulated
as a positive linear problem, unless the number of dual variables or the number
of constraints is exponential. In these cases one must use a separation oracle, since
only polynomially many flows can be handled. For positive linear programs, however,
the number of constraints is polynomially bounded and thus one can increase all dual
variables simultaneously. This is the approach taken by the algorithm of Luby and
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 3
Nisan [17]. This algorithm, which has both a fast sequential and parallel implemen-
tation, repeatedly performs a global median selection algorithm on the values of the
dual variables to choose a threshold, then increases values of dual variables above
this threshold. Although these algorithms have e#cient implementations, they both
perform global operations which make them unsuitable for fast distributed imple-
mentation, since emulating those global operations requires a polynomial number of
distributed rounds, and we are interested in much more time-e#cient solutions.
The only previously known result for a distributed flow control algorithm with
a global objective function is an algorithm of Awerbuch and Azar [3], which gives a
logarithmic approximation ratio and also runs in a polylogarithmic number of rounds.
Their algorithm is based on fundamental results from competitive analysis [2, 4]. The
deterministic algorithm we present produces (1 solutions to positive
linear programs, both in general and for the flow control problem, and builds on ideas
used in these other algorithms [3, 17, 19]. Our algorithm is most closely related to
the algorithm of Luby and Nisan, but eliminates the need for the complex global
selection operations and a global normalization step upon termination, enabling fast
implementation in a distributed setting. Those simplifications carry over to serial and
parallel settings as well, where we have a dramatically simpler implementation which
saves a 1
factor in the running time over the algorithm of Luby-Nisan. Finally, we
can parameterize the algorithm to quantify a tradeo# between the number of rounds
and the quality of the approximation. In practice, we can run the algorithm for any
number of phases, with the guarantee that after a constant number of phases, we
have a logarithmic factor approximation, and after a logarithmic number of phases,
we have a (1
The rest of the paper is organized as follows. We begin with a presentation of
our algorithm first as an easily understandable and implementable serial algorithm
for approximately solving positive linear programming in Section 2. In Section 2.3,
we prove that the algorithm achieves a (1 + #) approximation ratio, and we analyze
its running time. We formulate our distributed model and give an explanation of the
correspondence between flow control policies and positive linear programs in Section 3.
Then in Section 3.2, we present the distributed implementation applicable to the flow
control problem and explain the modifications to the analysis for this case.
2. Sequential Approximation Algorithms . We consider positive linear programs
represented in the following standard form, which is well known to be as general
as arbitrary positive linear programming.
#i,
We will further assume that the linear program (LP) is presented to the algorithm
in a normalized form in which the a ij are either 0, or satisfy 1
1. In the
4 Y. BARTAL, J. W. BYERS AND D. RAZ
sequential case, one can convert an arbitrary LP in standard form into an LP in
normalized form in linear time simply by dividing all constraints by
and setting
amin
, (where a 0}). We will describe how to
perform this transformation e#ciently in a distributed setting in Section 3.
r
do until (#F ) // Outer loop: Phase
do until (min Inner loop: Iteration
od
od
#j, output y
Fig. 2.1. The Sequential Positive LP Approximation Algorithm
2.1. Overview of Results. The parameterized algorithm for approximately
solving a positive linear program in normalized form is given in Figure 2.1. The main
theorem that we will prove about the performance of this algorithm relates the quality
of the approximation to the running time as follows.
Theorem 2.1. For any 0 < # 1 and 0 < r # ln(#m), the algorithm produces
a feasible (r )-approximation to the optimum primal linear programming
solution, and runs in O # nm ln( #m
r# time.
The following corollary clarifies the tradeo# between the running time and the
quality of the approximation and follows directly from Theorem 2.1.
Corollary 2.2. For any # 1, the algorithm produces a (1
to the optimum in O # nm ln( #m)
time. For any 1 # r # ln(#m), the algorithm
produces a approximation to the optimum in O # nm
r # time.
Proof. (of To prove the first claim of the corollary, set Theorem
2.1, and to prove the second, set choose # so that 0 < # 2-1
which implies r > 0 in Theorem 2.1.
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 5
2.2. Description of the Algorithm. In the sequential implementation of our
algorithm presented in Figure 2.1, the main body of the program in the bottom panel
runs in a sequence of phases, the number of which ultimately depends only on the
desired approximation ratio. Within a phase, values of appropriate primal variables y j
are increased monotonically until a threshold is reached. We refer to a set of increase
operations across all primal variables constituting the inner loop of our main program
as an iteration of our algorithm, noting that the number of iterations per phase may
vary. We will demonstrate that at the time slot t ending each phase, the non-negative
settings for the primal variables y j (t) and the dual variables x i (t) are primal and dual
feasible respectively, satisfying the constraints below.
Primal Feasibility: #i,
Dual Feasibility: #j,
2.2.1. Moving Between Pairs of Feasible Solutions. Since the values of
primal variables increase monotonically in our algorithm, it is crucial to carefully
select the variables to increase in each phase. To this end, our algorithm uses exponential
weight functions which have been employed in a variety of related contexts
including [2, 4, 17, 19, 3]. To do so, we associate each dual constraint with a measure
and we associate each primal constraint with a measure
Throughout the algorithm, the values of the dual variables x i
are tied to the values of "neighboring" primal variables y j by the exponential weighting
function defined in Update-Weights():
where # is a constant which again depends only on the desired approximation ratio,
and # is a scaling factor which is initialized to m, then grows geometrically with the
phase number until it reaches #F , which is the termination condition.
By establishing this connection between primal and dual variables, when the
value # j (t) is less than 1, the dual constraint # i a ij x i (t) # 1 is violated, but can be
satisfied by a su#cient increase in y j . This relationship suggests the following idea
for an algorithm, which we employ. Start with a pair of dual and primal feasible
solutions. Scale down the dual feasible solution by a multiplicative factor, making
the solution dual infeasible, and causing some dual constraints to be violated. Then
move back to a dual feasible solution by increasing those primal variables j for which
repeat the process until a satisfactory approximation is achieved.
A hypothetical depiction of the intermediate primal and dual feasible solutions
at the end of each phase relative to the value of the
optimal solution is shown in Figure 2.2. We maintain the invariant that the values of
the intermediate primal feasible solutions are monotonically non-decreasing over time,
but no such guarantee is provided for the intermediate dual feasible solutions. Linear
programming feasibility ensures that values of intermediate primal feasible solutions
are necessarily smaller than or equal to the value of the program, denoted by OPT,
and similarly, values of intermediate dual feasible solutions are necessarily larger than
6 Y. BARTAL, J. W. BYERS AND D. RAZ
or equal to the value of the program. Upon termination, we prove that the final (and
maximal) primal feasible solution is within a desired (in this case, 1 #) factor of
the minimal intermediate dual feasible solution. By linear programming duality, this
implies that the final primal feasible solution gives the desired approximation to the
value of the program.
In the sequential implementation presented in Figure 2.1, the bottleneck operation
is to recompute the # j s after each iteration, which takes O(nm) time. In fact, the
running time of this bottleneck operation can be more precisely written as O(E),
where E is the total number of non-zero entries of the constraint matrix of the linear
program. When multiplied by the total number of iterations, which we demonstrate to
be at most polylogarithmic in Section 2.3, we have the bound on the total sequential
running time.
Y
Y
Y
Y
Y
primal solutions
value
of
the
solution
OPT
time
dual solutions
Y
Y
Y
Y
Y*
Fig. 2.2. Intermediate Primal and Dual Feasible Solutions
2.3. Analysis of the Algorithm. In this section, we bound the approximation
ratio of our approximation algorithm, and present an analysis of its sequential running
time. We will later extend both of these results in a straightforward way to the
distributed case.
First we prove a claim we made earlier, that at the end of each phase both the
primal and the dual solutions are feasible. From the definition of the algorithm, the
values of primal variables increase monotonically, therefore the value of intermediate
primal solutions also increase monotonically. Thus to carry out the analysis of the
approximation ratio, it will remain only to prove that the value of the final primal
feasible solution and the value of the minimal dual feasible solution are at most a
(1+#) factor apart. In the proof we use the following three facts which all follow from
the initialization of the parameters given in Initialize-Parameters() in Figure 2.1.
Fact 2.3.
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 7
Proof. Immediately follows from the definition of # and from the fact that # 1.
Fact 2.4.
r
r
Proof. By definition,
and we have by definition,
we also have that # is a shorthand for 1/r), it su#ces to
show:
Now since r # ln(#m), we have that
O(ln(#m)), and the result follows directly.
Fact 2.5. e #
#.
Proof. Substituting #F for # and multiplying by e # , we must show
e
r+# or
e
r#
r+#
# or
e
r+#
r
Now by taking the natural logarithm of both sides above, we need to show:
Recall from the definitions that
r
r+#
Therefore, it is enough to prove the following.
Since P and # are clearly non-negative, and Q # 1, to show that # ln # Q+P
is non-negative we need P substituting for P ,
Using we have to
show
The final inequality follows from the fact that x # ln x, which completes the proof.
8 Y. BARTAL, J. W. BYERS AND D. RAZ
2.4. Feasibility. Recall that the algorithm maintains the invariant that dual
feasibility is achieved prior to each increase in #:
Fact 2.6 (Dual Feasibility). At the end of each phase, for all j, # j # 1.
We next prove that the y j s are primal feasible throughout the execution of the
algorithm, using Claim 2.7 to help perform the induction. In the proof it will be convenient
to treat the initial increase of y j s from 0 to their initialized value as iteration
2.7. For all i and for every iteration, # i #
Feasibility). For all i, # i # 1 throughout the execution of the
algorithm.
We prove these two claims simultaneously by induction over iterations of the
algorithm.
Proof. Let 0}. The first step is to prove that the claims hold for
iteration 0:
Since # this also implies that Claim 2.8 holds at iteration 0.
Consider a subsequent iteration, and let #v denote the change in variable v during
that iteration. We have that for all j, #y j # y j
by the rate of increase in an iteration,
so for all i,
where the final inequality holds by the inductive hypothesis of Claim 2.8. This completes
the proof of Claim 2.7.
To complete the proof of Claim 2.8, we consider two cases for # i separately. We
first consider values i for which # i
prior to an iteration. From the proof of
2.7 we have that after such an iteration, # i
< 1, giving the desired
result.
Next we consider those i for which # i
prior to an iteration. Fix such an
i and fix any j # J i . We have that:
a
By Fact 2.5, we have that by our choice of #, e #
#, and hence # j # a ij # 1, by
the definition of #. By the increase rule in the algorithm, we never increase the value
of primal variable y so in fact, no primal variable in J i increases in this
iteration. Therefore, # i does not increase during this iteration and remains smaller
than 1 by the induction hypothesis, completing the proof.
2.5. Proof of a (1 Approximation Ratio. We now turn to bound the
approximation ratio obtained by the algorithm stated as the first half of Theorem 2.1:
2.9. For any 0 < # 1 and 0 < r # ln(#m), the algorithm produces
a feasible (r )-approximation to the optimum primal linear programming
solution, We use the notation
#y j to denote the aggregate change in the
y values over the course of an iteration and similar notation for other variables. We
begin with the following lemma.
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 9
Lemma 2.10. For every iteration,
Proof. As # 1, we have from Claim 2.7 that # i # 1. It follows that
using the inequality e z
Prior to a given iteration, let is the set of indices of primal
variables which will be active in the upcoming iteration, i.e. those variables y j whose
values will increase in the iteration. (Recall that a variable y j may be increased several
times in a phase). The lemma follows from the following sequence of inequalities:
The final inequality holds from the definition of S.
In stating and proving the next lemma, we require a more precise description of
our notation. We now consider the change in the values of the dual variables X over
the course of a phase. In the proof, we let X # denote the sum of the x i at the end of
the current phase, and we let X denote the sum of the x i at the end of the previous
phase, i.e. before they are scaled down. We let #X denote the change in a the sum of
the x i over the course of the current phase. We further define X # to be the minimum
over all dual feasible solutions obtained at the end of each phase and let YL be the
primal feasible solution obtained at the end of the final phase. Fact 2.6 and Claim 2.8
respectively imply that X # is dual feasible and YL is primal feasible. In conjunction
with Lemma 2.11 below, this implies the approximation result stated in Claim 2.9,
by linear programming duality.
Lemma 2.11.
Proof. We prove the lemma for two separate cases; the first being an easy case
in which the initial primal feasible solution is a close approximation to the optimum,
and the second where we repeatedly apply Lemma 9 to bound the ratio between X #
and YL . Let X 0 denote the value for X before the initialization of the y j s, that is
Y. BARTAL, J. W. BYERS AND D. RAZ
the value for X after the first phase. Similarly,
let XL denote the value of the dual solution at the end of the final phase.
Case I: XL # r+#
Letting Y 1 denote the value of the primal solution at the end of the first phase, we
apply Lemma 9 to the iterations comprising the first phase, giving:
Since the values of the primal feasible solutions increase monotonically throughout
the course of the algorithm the Lemma holds by the following sequence of inequalities:
Case II: XL > r+#
the values X are scaled by a #
factor
just following the end of each phase, the earlier definitions imply that:
+#X.
By rewriting this expression and applying the inequality e z
using X # X and applying Lemma 2.10 yields
#L to be the initial value of # and the value of # in the last phase of the
algorithm, i.e. #L < #F . Using the bound above repeatedly to compare XL with X 1
gives us:
Since XL is dual feasible and the optimal solution is bounded below by 1 (by
the normalized form of the program) we have that XL # Also note that
by the assumption r # ln(#m), we have # (r #). We can now use these facts in
conjunction with the fact that XL > r+#
Using the bound above in (2.1) and observing that # #) we
get
e
r+#
r+#
r+#
r+#
r+#
where the final inequality holds by substituting using # 1. We
therefore get
YL
concluding the proof of the Lemma for Case II.
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 11
2.6. Running Time. For the algorithm provided so far, we have the following
running time bounds, which are slightly weaker than those stated in Theorem 2.1.
These weaker bounds are presented since a natural translation of these time bounds
and the preceding analysis extends directly to the distributed algorithm which we
present in Section 3. After proving these bounds, we provide a simple improvement
which applies only in the sequential case and which is used to give the time bounds
stated in Theorem 2.1.
2.12. The sequential algorithm runs in O # (r+1)nm
r
r#
time.
Proof. We bound the number of phases by measuring the change in #, which
increases by a (1 + #) factor per phase. From the definitions in Figure 2.1, and using
Fact 2.4 for the final equality, we have that:
# log 1+#F
r+#
r+#
r
r#
# .
We now bound the number of iterations in a phase by computing the maximum
number of iterations needed to increase all # j values above 1. For a given j, we
say that y j is large once y j #
ln(#). We show that once y j is large, # j # 1, and
therefore j no longer participates in the phase. Let the set I
for all i # I
a ik y k ##
ln(#) and
Initially,
and at every iteration it increases by a factor of 1+ #
. Therefore
the number of iterations y j can participate in before y j becomes large is at most
# log 1+ #
.
From Fact 2.5 we have O(#). By using this fact and by another application
of Fact 2.4, we bound the number of iterations during a phase by:
O #
r#
r
O
r#
r#
# .
Note that the term r+1
r
cannot be removed since r can be any value satisfying 0 <
r # ln(#m). Multiplying this by the earlier bound on the number of phases and using
the fact that each iteration can be computed in O(nm) time, this completes the proof
of Claim 2.12.
To prove the time bound stated in the second half of Theorem 2.1, we need to
give a sequential algorithm which completes in O # nm ln( #m
r# time. This running
12 Y. BARTAL, J. W. BYERS AND D. RAZ
time can be achieved by an algorithm which performs exactly one iteration per phase.
In the sequential case, we accomplish this by increasing a candidate y j not merely by
a multiplicative factor of 1+ #
per iteration, but by increasing it by the amount which
causes # j to reach a value of 1 directly. (Note that this procedure is straightforward to
implement in the sequential case, but not in the distributed case). This improvement
causes each phase to terminate in a single iteration, Claims 2.7 and 2.8 still hold (the
other claims are una#ected), and we achieve the time bound stated in Theorem 2.1.
3. The Distributed Model. We now consider the following model in the spirit
of Papadimitriou and Yannakakis [18] in which distributed agents generate approximate
solutions to positive linear programs in the standard form presented in Section 2.
We associate a primal agent with each of the n primal variables y j and a dual
agent with each of the m dual variables x i . Each agent is responsible for setting the
value of their associated variable. For any i, j such that a ij > 0, we say that dual
agent i and primal agent j are neighbors. In each distributed round of computation,
each agent may broadcast a fixed-size message to all of its neighbors, i.e., in one
round each primal agent j may broadcast one message to its set of dual neighbors
I and each dual agent i may broadcast one message to its set of primal
neighbors
After a fixed number of rounds, the agents must choose feasible values for their
variables to minimize (in the case of the primal) the approximation ratio: OPT
where OPT is the value of the optimal solution to the LP. We then study the tradeo#
between the number of rounds and the quality of the approximation ratio obtained.
The application of flow control in a network with per-flow queuing motivates the
following mapping to our model of primal agents and dual agents. Each of n connections
transmits data along a fixed path in the network, and a connection corresponds
to a primal agent. Each of the paths traverse an ordered subset of the m routers
which comprise the network, and these routers correspond to dual agents. At a given
time step t, each connection j transmits at a given rate into the network, thereby establishing
the value y j (t) of its primal variable. Once these new flow values stabilize,
each router i uses its local load to set a value for the primal variable x i (t). Based on
a simple function (the sum) of the values of dual variables along its path, the source
uses this control information to compute a new flow value y 1). To compute this
sum, each connection transmits a fixed-length control message which loops through
the routers along its path and back to the source. As mentioned earlier, this simple
and natural model of communication between connections and routers corresponds to
models previously suggested in both practical and theoretical studies of flow control
[3, 1, 5, 16].
Each router i has capacity C i , which it may share among the connections which
utilize it, while each connection accrues benefit B j for every unit of end-to-end capacity
which it receives. Therefore, the connections act as the primal agents and the
routers act as the dual agents in the following positive linear program.
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 13
Router-Initialize
Router-Update
send
Router-Initialize i ();
do until (all
Router-Update i ();
do until (all j # J i end phase)
for all active connections
call Router-Update i ();
od // End of phase
od
Fig. 3.1. The Distributed Algorithm at Router i
Clearly, this positive linear program can be converted to standard form by the
local operation a
. In a synchronous model, each round takes time equal to
the maximum round-trip time experienced by a connection in the network. However,
this synchronization assumption can and will subsequently be relaxed with no changes
to the algorithms we propose. A final note is that the message size we use in our
implementation can be bounded by a number of bits polynomial in log m, log # and
1/#.
3.1. The Distributed Approximation Algorithm. Several additional complications
must be addressed in the definition and description of the distributed algorithm
provided in Figures 3.1 and 3.2 for routers and connections respectively. Since
global operations cannot be performed e#ciently, each connection and router must
be able to independently compute the values of all of the parameters described in the
serial implementation. In the case of parameters which are fixed, such as the value
of m (the number of nodes in the network), and for the parameters which a#ect the
approximation ratio, r and #, we assume that these values are known in advance to
all connections and routers. We do not assume that n, the number of connections,
is globally known. In the sequential case, knowledge of this parameter was required
to initialize the variables y j so as to satisfy Claims 2.7 and 2.8. In the distributed
setting, each connection j instead computes a local estimate of n, which it can
compute in two distributed rounds, and which then used in initialization satisfies
Claims 2.7 and 2.8. Finally, the parameter # used to convert the program into normalized
form may not be globally known, in which case the linear program cannot
be normalized e#ciently. Approximately solving such programs in the distributed
setting adds considerable complexity, and we defer providing techniques for doing so
until Section 3.2.
Connections and routers communicate using the message-passing model described
14 Y. BARTAL, J. W. BYERS AND D. RAZ
I
send i#I j
send
read i#I j
As defined in Figure 2.1
Phase counter
do until (#F )
Iteration counter (within a phase)
do until
od // End of phase
od
output y j and terminate;
Fig. 3.2. The Distributed Algorithm at Connection j
in Section 3. As in the serial algorithm, agents track time in terms of phases and it-
erations. When transmitting the value of a variable using the send primitive, agents
timestamp the transmission with their current phase number p and iteration t. Like-
wise, in receiving the value of a variable using the read primitive, agents specify their
phase number p and iteration t, and wait until they receive the appropriate value. For
simplicity, we assume that these control messages reliably flow through the path, although
in practice, retransmissions would likely be necessary. Also, strict alternation
between primal and dual rounds eliminates the possibility of deadlock.
In our implementation, message-passing primitives enable control to alternate
between connections and routers at a local level. This is not to say that control is
globally synchronized - in fact, at any instant in time, connections in separate areas of
the network might not even be working on the same phase. However, it is the case that
any given router is working on only a single phase at an instant in time. Therefore,
all the connections through a router which is currently working on phase i are either
actively working on phase i themselves or are idle and awaiting permission to proceed
to phase i + 1. Aside from message-passing, the other technical obstacle in converting
the centralized algorithm to a distributed algorithm is the condition for ending a
phase. In the centralized algorithm, a phase terminates when min k # k # 1. Since we
cannot hope to track the value of this global expression in our distributed model, we
instead let each connection j check whether # j # 1 locally and independently. When
the condition is satisfied, connection j terminates its phase, by incrementing its phase
number and informing its neighboring routers.
The analysis of feasibility and the bounds on the quality of the approximation are
identical to those for the centralized algorithm. This is the case because the value of
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 15
any primal variable at the time that the corresponding connection completes phase
satisfies the conditions placed on primal variables after phase i in the centralized
implementation. A similar statement holds with respect to the values of dual variables
at the time their corresponding routers complete phase i. These statements hold for
each primal and dual variable independently, and irrespective of the fact that phase
completion times may not occur uniformly across the network. As for the distributed
running time, the following corollary to Claim 2.12 holds:
Corollary 3.1. The distributed algorithm runs in O # (r+1)
r#
rounds.
3.2. Distributed Techniques to Convert to Special Form. Recall that
we can convert a program in standard form to the normalized form by dividing all
constraints by amax , thereby setting
amin
. If bounds on the values of amax and
a min are known in advance, for example if connections and routers can all bound
the min and max values of the edge capacities and benefit coe#cients, then # can
be estimated. But these bounds may not be globally known, moreover, the value of
#, which impacts the running time of our algorithm, depends on the values of the
entries of the matrix. We now show that solving a problem in standard form can be
reduced to solving problems in a special form (similar to a form used by Luby and
Nisan in [17]) where the value of # depends only on m and # and does not a#ect the
approximation ratio obtained nor does it significantly a#ect the running time of our
algorithm. Moreover, this transformation can be done distributively in a constant
number of rounds, without global knowledge of amax and a min .
A precondition for transforming an LP Z in standard form to an LP Z # in special
form is that we can generate a feasible solution for Z with value c which approximates
the value of the optimal solution for Z to within a factor of # : c # OPT # c# . If this
precondition is satisfied, we can perform the following transformation, which bounds
the value of the a # ij
in Z # by # 2
. Note that
the value of # now depends on the extent to which we can bound the value of the LP,
but not on the relative values of the constraints (which could be very small).
c#
, and perform the following transformation operation on the constraints

#c
c#
otherwise
This transformed LP has the following properties:
1. If {y #
j } is a primal feasible solution for Z # then
such that a #
otherwise
is primal feasible for Z, and # j y
2. If {y j } is primal feasible for Z then # y #
1+# is primal feasible for Z # , and
3. #
Property 3 is clearly true, but the other two properties require the short proofs below.
Y. BARTAL, J. W. BYERS AND D. RAZ
Proof. (of Property 1)
Take a feasible solution {y #
j } for Z # and let {y j } be as specified. Then for any
fixed value of i,
# 1.
The final inequality holds by the feasibility of the solution {y # j }, so the solution {y
is feasible for Z. The value of this solution satisfies:
The first inequality holds by the fact that for any feasible {y #
} and for any i and j,
1. The second inequality holds by the bound on the number of routers in the
network, and the final inequality holds by the definition of #.
Proof. (of Property 2)
Take a feasible solution {y j } for Z and let {y # j } be as specified. Then for any
fixed value of i,
c#
c#
c#
c#
The final line holds from the bound on the optimal solution for Z:
c# , so the solution y #
is feasible.
Now we generate an approximate solution to Z by performing the transformation
to special form and then computing a (1 using our
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 17
algorithm. We transform this solution to {y j } using the transformation described in
property (1) and get a primal feasible solution Y for our LP such that:
The first inequality is from property (1), the second is based on the fact that
{y #
j } is a (1 #) approximation to the value of Z # (denoted by OPT # ) and the final
inequality is from property (2).
Next we need to explain how to choose the parameters c and # as to guarantee
the precondition: c # OPT # c# . Recall that I j denotes the set of edges incident to
connection j: I denotes the set of connections incident to edge
k#I l
a kl
a quantity which can be locally computed in one round for each router i. Also, let
for each connection j, define
# i . It is relatively easy
to show that 1
. The first inequality holds from the primal feasibility
of the solution in which the connection j used in the evaluation of the minimum # i
is assigned flow y
. The second inequality holds from the dual feasibility of the
solution in which each router i is assigned weight x
Therefore, we can set
, and in the sequential implementation, giving
and an O # nm ln(m/r#)
r# running time.
3.3. Approximating # in the Distributed Setting. In the sequential case,
knowledge of # is enough to perform the transformation to special form, but connections
and routers may not know this value. We now describe a technique in which
we distributively subdivide the LP into subprograms based on local estimates of #.
The value of each subprogram is bounded, so we can work in special form. Then,
we recombine solutions in such a way as to only assign non-zero rates to connections
with good estimates of #, but we prove that this only reduces the sum of the rates by
a small factor.
# and for define the sets
G q
for integer t. It is clear that each connection belongs to exactly p of these sets.
Independently for each value of q, each router i assigns flow only to connections
which are members of G q
, where T iq is the minimal value of t for which G q
non-empty. In e#ect, this means that the algorithm is run on the network p successive
times. From the connection's point of view, it runs p successive algorithms, using # j
as an approximation for #. In each of these p trials, it can be rejected (i.e. given no
flow) by some of the routers. The final flow assigned to connection j is the average
of the flows given in the p independent trials. We will prove that this procedure does
not decrease the sum of the rates by more than an additional (1 - #) 2 factor.
Y. BARTAL, J. W. BYERS AND D. RAZ
Now define OPT(X) to be the value of the modified LP when flow can only be
assigned to connections in the set X. It is not di#cult to show that OPT(G q
bounded between #
m. Thus, we have that for
each set G q
, the special form of the modified LP for connections in G q
satisfies the
precondition with
m. Therefore, for each of these
LPs, we can use
# 2+1/# .
We now turn to bound the approximation ratio. Consider a particular q #
{0, . , p - 1}, and let T and Q be the unique integers such that # is in the interval
defined by G q
. For q #= Q and for the dual feasible
setting {x
G q
i|i#I l ,l#G q
This implies that OPT (G q
Q. The quality of the solution
we obtain is therefore bounded below by:p #
Putting everything together, we have a distributed algorithm that assumes global
knowledge only of m and the approximation parameters r and #. This algorithm finds
a primal feasible (r )-approximation of the optimal solution, and terminates
in O # (r+1)
distributed rounds.
4. Discussion. We studied the problem of having distributed decision-makers
with local information generate feasible solutions to positive linear programs. Our
results explore the tradeo# between the amount of local communication that these
agents may perform and the quality of the solution they obtain, measured by the
approximation ratio. While we have provided an algorithm which obtains a (1
#) approximation ratio in a polylogarithmic number of distributed communication
rounds, proving non-trivial lower bounds on the running time needed to obtain a
approximation remains an open question, as does the challenging problem of
providing fast approximation algorithms for general linear programs.

Acknowledgments

. We would like to thank Christos Papadimitriou for stimulating
discussions and useful insights in the formulative stages of this work. We also
thank Dick Karp, Mike Luby, Dorit Hochbaum and the anonymous SICOMP referees
for their helpful comments on earlier versions of results presented in this paper.
FAST APPROXIMATION ALGORITHMS FOR POSITIVE LPs 19



--R

Convergence Complexity of Optimistic Rate Based Flow Control Algorithms.

Local Optimization of Global Objectives: Competitive Distributed Deadlock Resolution and Resource Allocation.
Throughput Competitive On-line Routing
Converging to Approximated Max-Min Flow Fairness in Logarithmic Time
Achieving Global Objectives Using Local Information with Applications to Flow Control
Data Networks.
Potential function methods for approximately solving linear programming prob- lems: Theory and Practice
The Rate-Based Flow Control Framework for the Available Bit Rate ATM Service
Maximizing Throughput of Reliable Bulk Network Transmissions.
An Algorithm for Rate Allocation in a Packet-Switching Network with Feedback
Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems.


Distributive Graph Algorithms - Global Solutions from Local Data
Optimization Flow Control I: Basic Algorithm and Convergence.
A Parallel Approximation Algorithm for Positive Linear Programming.
Linear Programming without the Matrix.
Fast Approximation Algorithms for Fractional Packing and Covering Problems.
--TR
primal-dual;linear programming;approximation algorithm;flow control