WorksComputer Science
Multiplicative Weights for Mixed Block Constraints and Maximum Multicommodity Flow
Abstract
We study multiplicative-weights (MWU) algorithms for block-separable feasibility problems containing both packing and covering constraints. Each iteration optimizes a weighted linear objective over one block, either chosen uniformly at random or visited in a fixed cyclic order. We show that the cyclic algorithm returns an -approximate solution after oracle calls where is the number of blocks and is the width of the oracle. The same holds for the randomized version with high probability. Previously, such bounds were shown when the coupling constraints have the same sign [Radzik'95; Villavicencio-Grigoriadis'96]. These analyses critically depended on monotonicity arguments that are not available in the mixed case. As an application, we obtain a deterministic -approximation for maximum multicommodity flow (M-MCF) using approximate single-commodity min-cost-flow calls. For planar graphs, and more generally for graph families admitting a near-linear-time min-cost-flow algorithm, this gives total running time . Compared with the algorithm of [Chen-Graur-Sidford'25], this improves the dependence on for these graph families at the cost of a worse dependence on . Finally, we give an exponentiation-free finite-precision implementation of the cyclic algorithm. It represents each internal weight by a logarithmic-bit mantissa and exponent, while every price supplied to the block oracle is rational and has a polynomially bounded common denominator.
Introduction
This paper considers the following block-structured feasibility problem:
Here is a convex set, is a matrix, and . Thus, we allow both packing constraints of the form and covering constraints of the form . We are interested in computing -approximate solutions; these are points satisfying .
Let us define and . We assume access to procedure that has the following specification.
Input. A block and a vector , where is the simplex in .
Output. A point that satisfies the following:
Here is the width parameter.
We analyze two natural versions of the Multiplicative Weights Update algorithm for solving this problem: randomized (MWU-R) and deterministic (MWU-D). The first one selects the block uniformly at random at each step, while the second processes the blocks in a cyclic, or round-robin, order. Our main result is
Theorem 1. For any value , MWU-D either returns an -approximate solution or correctly reports that (1) is infeasible after oracle calls. The same holds for MWU-R after oracle calls with probability at least .
Moreover, assuming that all numerical input data and oracle outputs are rational numbers of polynomial bit length, MWU-D can be implemented so that every internal weight is represented with bits. Its oracle calls can be restricted to vectors , where , , and .
Multicommodity flow problem
To motivate our work, consider two applications: the concurrent multicommodity flow problem (C-MCF) and the maximum multicommodity flow problem (M-MCF). Given a capacitated graph and pairs of terminals , the goal is to find - flows for each that can be routed in simultaneously. In their simplest forms, M-MCF asks to maximize while C-MCF additionally imposes the constraint that is the same for all .
Using a standard reduction to the feasibility problem (with a binary search on the objective value ), both problems can be cast in the form (1). Importantly, we have in the case of C-MCF and in the case of M-MCF, where the last coordinate represents the covering constraint . The oracle for a given commodity needs to approximately solve a minimum-cost flow problem in a certain graph.
The work of Grigoriadis and Khachiyan [11] and Leighton et al. [20] showed that C-MCF can be solved by a randomized algorithm using oracle calls, either with high probability or in expectation. As in MWU-R, they select blocks (i.e. commodities) randomly. Radzik then proved in [27] that replacing uniform sampling with a round-robin selection gives the same bound. The same cyclic derandomization was extended to general problems of the form (1) with by Villavicencio and Grigoriadis [31], who also allowed each sweep to visit the blocks in an arbitrary order. Note that the results of [11, 20, 27, 31, 13] do not cover M-MCF; their analyses rely on the fact that all components of the right-hand side in (1) have the same signs.
Our main contribution is the analysis of randomized and cyclic one-block-at-a-time algorithms for mixed packing and covering constraints, with bounds stated in terms of individual block-oracle calls. The analyses of [11, 20, 27, 31, 13] obtain this bound when all coordinates of have the same sign. Extending the randomized argument to mixed signs is relatively simple and requires only an additional one-sided residual bound. However, the deterministic extension is much more challenging. The analyses in [27, 31] rely heavily on monotonicity properties that fail in the mixed case. Our proof uses a very different technique, and is the main technical contribution of this work.
By applying Theorem 1 to M-MCF and using binary search we obtain the following result.
Theorem 2. Consider a directed or undirected M-MCF instance with edges, nodes and commodities whose capacities and rewards are polynomially-bounded nonnegative integers. There is a constant and a deterministic algorithm that for a given returns a feasible flow of value at least using single-commodity minimum-cost-flow calls. Every call has nonnegative rational costs of bit length and is allowed to return a feasible flow of cost at most times the minimum cost.
| year | work | flags | complexity | restrictions | technique |
| 1987 | Shahrokhi-Matula [28] | C | uniform capacities | MWU precursor | |
| 1990 | Klein et al. [19] | C | uniform capacities; randomized | ||
| 1991 | Plotkin-Shmoys-Tardos [25] | CM* | randomized | ||
| CM* | |||||
| 1998 | Garg-Könemann [10] | CM | MWU | ||
| 1999 | Fleischer [8] | M | |||
| 2002 | Karakostas [17] | C | implicit | ||
| 2010 | Madry [22] | M | randomized | ||
| 1991 | Leighton et al. [20] | C | randomized | ||
| C | |||||
| 1995 | Radzik [27] | C | block MWU | ||
| 1995 | Grigoriadis-Khachiyan [13] | C* | |||
| 2026 | this work | M | |||
| M | efficient vertex separator | ||||
| 2017 | Sherman [29] | C | undirected | area-convex | |
| 2025 | Chen-Graur-Sidford [4] | CM | optimization |
Table 1. Selected approximation results for concurrent and maximum multicommodity flow. C/M flags indicate whether the complexity applies to C-MCF, M-MCF, or both. A superscript * denotes a cost-constrained or minimum-cost variant. is the complexity of a single-commodity min-cost-flow computation. The notation also hides factors logarithmic in .
The current best-known algorithm for -approximate maximum weighted multicommodity flow, due to Chen, Graur, and Sidford [4], runs in . Combining Theorem 2 with the -time exact min-cost-flow algorithm of Chen et al. [5] instead gives time. This has a worse dependence on than the algorithm of [4], but leaves a possibility of improving the dependence on from almost linear () to nearly linear (), if the complexity of an approximate min-cost flow solver is ever improved to nearly linear time. In fact, a nearly linear time (exact) min-cost flow algorithm is known for planar graphs, or more generally graph families that admit an efficient vertex separator of size [7]. Consequently, our work yields an -time algorithm for -approximate M-MCF in such families. We remark that our approach is a short black-box reduction to single-commodity min-cost flow, whereas the better dependence on in the algorithm of [4] relies on more specialized machinery.
Other related work
Multicommodity-flow algorithms Existing algorithms for C-MCF and M-MCF can be grouped into three categories: MWU-type algorithms that use shortest path computations as the underlying oracle [28, 19, 25, 10, 8, 17, 22], block-MWU algorithms that rely on a min-cost-flow solver [20, 27, 13], and techniques based on optimizing an area-convex functional [29, 4]. Table 1 summarizes the complexities of these approaches. The general exponential-potential and price-directive decomposition frameworks underlying the Grigoriadis-Khachiyan flow result are developed in [12, 14].
Block-oracle models Problem (1) with was studied by Grigoriadis and Khachiyan [11]. For a constant block-solver tolerance, their randomized algorithm uses expected block-solver calls. Their deterministic algorithm has the same number of outer iterations, but every iteration makes parallel block-solver calls. Leighton et al. [20] instantiate the same principle for concurrent multicommodity flow by randomly selecting a commodity, whereas Radzik [27] replaces random selection by a fixed round-robin order in that setting. Villavicencio and Grigoriadis [31] establish cyclic derandomization for this general block model with nonnegative coupling constraints. Thus, when , they obtain the same asymptotic deterministic cyclic bound as Theorem 1; their stated bound is block-solver calls.1 This common-sign structure permits a monotone potential argument. The present analysis retains the black-box block oracle and cyclic order while allowing both packing and covering rows.
General packing and covering More generally, multiplicative-weights and Lagrangian-relaxation methods have long been used for packing and covering problems; Arora, Hazan, and Kale [1] give a broad survey. In particular, for , the mixed-sign guarantee follows from their standard MWU framework for convex feasibility with an asymmetric bounded oracle; see [1 Theorems 3.3-3.5]. Alternative width-independent bounds for , under different global oracle specifications and for more general convex packing and concave covering functions, were given by Jansen [15] and Diedrich and Jansen [6]. Plotkin, Shmoys, and Tardos [25] developed an oracle-based framework for fractional packing and covering. Young [32] and Quanrud [26] studied MWU algorithms for explicitly represented mixed packing and covering LPs, without the block-oracle structure assumed here. In particular, Young gave sequential and parallel width-independent algorithms, while Quanrud obtained a deterministic algorithm with nearly linear running time. For pure packing and covering, Klein and Young [18] proved an lower bound for Dantzig-Wolfe-type algorithms in the applicable parameter regime. Thus, for , the dependence of Theorem 1 on , , and is optimal for that class of algorithms; their result does not address the dependence on or the restriction to cyclic individual-block updates.
Bit complexity
To achieve the bit-complexity claim in Theorem 1, we store each internal weight as a floating-point number with logarithmic-bit mantissa and exponent, rounding it multiplicatively after every update. This accommodates the potentially exponential dynamic range of the weights. Prices passed to the oracle are instead ordinary rationals with logarithmic-bit numerators and a common denominator, obtained by truncation before normalization. We call this a hybrid weight-price representation. We are not aware of earlier MWU work that explicitly uses this representation.
For MWU variants with exponential updates, an alternative would be to maintain rounded rational logarithms of the weights. The update then consists of rational addition followed by rounding to a fixed grid; exponentiation is needed only when computing the normalized prices. Hedge [9] is a basic example of this exponential-update viewpoint. Implementations of the exponentiation step, including softmax and matrix-exponential computation, have been studied in [2, 16, 30, 24, 23, 3]. In general, these works do not ask whether both the maintained state and the normalized prices supplied to a black-box oracle can be represented by rationals of logarithmic bit length with a short common denominator.
Grigoriadis and Khachiyan [11 Section 9.1] form prices by normalizing exponentials of the current resource loads and explicitly address the price side of this question. They state that their general block algorithm retains its iteration bound when the normalized price components are computed to logarithmic precision; the remaining bit analysis depends on the block solver. Their minimum-cost-flow application rounds prices to a rational grid of logarithmic bit length [13].
An exponentiation-free special case is Weighted Majority with : its weights are powers of two encoded by logarithmic-bit mistake counts and updated by binary shifts [21]. It has no optimization oracle, so it does not address the representation of oracle prices.
Algorithm and guarantees
For a sequence of selected blocks , write
Algorithm 1: MWU for block-separable feasibility.
1 set $w^{(1)} = \mathbf{1} \in \mathbb{R}^{m}$
2 for $t = 1,\ldots,T$ do
3 choose $i_t \in [k]$
4 $x^{(t)} \leftarrow \operatorname{Oracle}(i_t,y^{(t)})$ with $y^{(t)} = w^{(t)}/\sum_e w_e^{(t)}$
5 set $r^{(t)} = A_{i_t}x^{(t)} - b/k$
6 set $w_e^{(t+1)} = w_e^{(t)}(1+\eta r_e^{(t)})$
7 return $x=(x_1,\ldots,x_k)$ where $x_i = |\mathcal{T}_i|^{-1}\sum_{t\in\mathcal{T}_i}x^{(t)}$
MWU-R chooses every independently and uniformly from . MWU-D uses the deterministic rule .
Theorem 3. Suppose that (1) is feasible, , , , and . Then MWU-R outputs a -approximate solution with probability at least .
Theorem 4. Suppose that (1) is feasible, , , and is a multiple of . Then MWU-D outputs a -approximate solution.
Bit complexity Vectors in Algorithm 1 may grow to rational numbers requiring polynomially many bits to store. Next, we discuss how this can be avoided.
For integers , define
Thus, numbers in can be represented with bits ( bits for the exponent and bits for the mantissa). For value let be a number in of the form with ; clearly, such number always exists. Finally, define
We extend these operations to vectors by applying them componentwise.
Theorem 5. Suppose that (1) is feasible, , , and is a multiple of . Use the block oracle with additive accuracy . Consider the following modification of MWU-D: (1) compute at line 4 as follows: set , , and ; (2) after computing at line 6, update . If and with appropriate constants, then MWU-D produces a -approximate solution after oracle calls. During the algorithm all weights belong to for , while every oracle vector has the form , where , , and .
Note that Theorem 1 follows from the theorems above by running the algorithms for the specified number of iterations, checking the returned point, and reporting infeasibility if the check fails.
Proofs of Theorems 3, 4, and 5
By convexity of sets , the output of Algorithm 1 satisfies .
For let us define
The proofs will follow the usual strategy used for MWU: first, we prove that potential does not grow too fast with , and then for each we will use condition to conclude that .
The oracle specification implies that
Consequently,
Analysis of MWU-R
Upper-bounding Let be a feasible solution. Approximate optimality implies
Let be the history before is sampled and set . By (5),
Because , it follows that
Iterating from gives
Markov’s inequality therefore gives
with probability at least .
Proof of Theorem 3 Fix , and define . Suppose that . Using eq. (4) and bound , we get
Combining (6) and (7) and then using definitions of and yields
If , then holds automatically. Thus for every . Chernoff’s inequality and a union bound show, with probability at least , that
Assume that (6) and (8) are both true; this holds with probability at least . By the definition of and ,
For we have and . Therefore,
Similarly, for we have and . Therefore,
Analysis of MWU-D
Upper-bounding We start with the following result.
Lemma 6. There exists a vector such that
Proof. For each block, define
By the width conditions, is contained in a bounded box; since it is closed by definition, it is compact. Hence is a closed convex upper set. For every , there is a satisfying . Indeed, otherwise strict separation of from the closed convex upper set would give a separating vector , since the set is upper closed. Normalizing gives and
contradicting approximate oracle optimality. Also, for every and , : this holds for the convex hull because is convex and extends to its closure by continuity. Fix a feasible tuple and choose with . Initially set
Feasibility of and the choice of the give
Moreover, every vector in satisfies on and on . Thus the initial vectors satisfy on and on . Increase coordinates of the until (9a) holds. On this preserves (9b). On it can be done while preserving (9c): the total available increase is at least the required increase .
It remains to show (9d). First consider the initial vectors , before any coordinates are increased. For , since , we have . Approximate optimality of therefore yields
Since , multiplying by gives
Using and the initial definition , we therefore obtain
which is (9d). Increasing preserves this condition because .
Fix a vector given by Lemma 6. Since for each , we conclude that there exists a -periodic sequence satisfying . By adding a constant to we can assume that for and for . Conditions (9b) and (9c) now imply that on and on . We can write
The update rule implies , and hence
Conditions for and for now imply
Here we extended both sums from to , which is valid because the added summands are nonnegative. We have and , and hence . Define
Thus and collect the positive and negative parts, respectively, of the residual contributions. Summing the two bounds in (10) over their respective coordinate sets gives
Finally, summing (15) over and substituting the preceding bound yields
The update rule also gives
The last two identities give and . Substituting these identities into (18) and collecting the and terms yields
We can write
(The first bound holds since and hence .) Dividing (19) by and using (20) gives
Iterating this recurrence starting from gives
where the first inequality is proved by induction on .
Proof of Theorem 4 Fix , and again define . Suppose that . As in eq. (10), we get
Comparing (21) with (22) gives
Recall that and . We first claim that
This holds since the denominator is positive and the difference of cross products is negative:
We also have , and , and hence
Substituting these bounds into (23) gives
We established bound (24) assuming that . If then the same bound holds automatically. Thus, (24) holds for all . This finally implies
Finite-precision implementation: proof of Theorem 5
Let and be the weights and the oracle vectors in the modified algorithm, and be the oracle answer in the -th step. Let and be similar quantities in the execution of the original MWU-D algorithm with parameter in which the oracle returns in the -th step. It suffices to show that this answer fits the specification of the approximate oracle, i.e. that
for each and . Theorem 4 will then imply that the output is an -approximate solution.
Since the two executions use the same oracle answer , they also use the same residual . By construction, we have and
for some with . This implies that
for each . Next, we compare and . Recall that they are constructed from and as follows:
We choose the constant in so that . Since some coordinate of is at least , at least one coordinate survives the truncation; hence and is well defined.
The definitions of and will not change if vectors and are divided by the same constant; this operation will also preserve (26). We can thus assume w.l.o.g. that . This condition together with (26) implies and hence . Choose the constant in so that ; then . Choose the constant in so that . We obtain
Since and under our normalization, we obtain
Let where the subscript indicates the oracle’s accuracy. (Recall that .) The width bounds and (27) imply
Using this estimate and the oracle guarantee at and , we obtain the desired inequality (25):
It remains to discuss the ranges of and in the modified algorithm. First, , so the exponent of an internal weight has bits. Together with the -bit mantissa produced by rounding, this gives the stated membership in .
We next consider . Any two nonzero coordinates of differ by a factor of at most : each is at least , while each is at most . Write every nonzero rounded weight in canonical dyadic form with (absorbing powers of two into ). The preceding ratio bound implies for nonzero retained coordinates. After factoring out , the retained weights are integers having bits. Therefore
where both and have bits. This gives the stated polynomially bounded shared denominator.
Maximum weighted multicommodity flow
In this section we apply Theorem 1 to prove Theorem 2. Let be a directed or undirected graph with capacities . Commodity has terminals and reward per unit of flow. Edges of zero capacity and commodities of zero reward can be discarded, so these positivity assumptions are without loss of generality. For a candidate objective value , let consist of pairs such that is an - flow of value , for every , and . The feasibility problem for value can be written as follows:
This target system is feasible if and only if . The definition of implies that any vector satisfies conditions (2b), (2c) with width parameter . Given prices , the -th oracle needs to solve
where is the component corresponding to constraint (21c). (We shifted the objective by , which does not affect the oracle and its additive approximation guarantees). Note that for any since .
We can model (22) as a min-cost flow problem as follows. Define . Add a parallel dummy edge (directed or undirected, depending on the type of the multicommodity flow problem), and seek a minimum-cost - flow of value exactly in the resulting graph. Give every original edge capacity and cost , and give the dummy edge capacity and cost . If units use the original graph, the remaining units use the dummy edge, and the resulting cost is exactly . Thus all costs in this min-cost-flow instance are nonnegative. In the undirected case, cancel cycles in the returned flow before reading off . In particular, any backward use of the dummy edge forms, together with an - path in the original graph, a nonnegative-cost cycle and can be removed without increasing cost. We may therefore assume that the dummy edge carries an amount in in the forward direction, so the remaining original flow has value as required.
Sending all units through the dummy edge has cost , so . Hence, if the min-cost-flow solver finds feasible flow within factor from the optimum then its additive error is , as needed:
We showed that a feasible target can be tested with min-cost-flow calls; if problem (21) is feasible then we find an -approximate solution. Scaling all flows uniformly makes the capacity constraints exact while retaining total reward of the flow at least .
This is a gap test: an infeasibility report implies , whereas a returned solution can be scaled to a feasible flow of value . Treating these outcomes as the upper and lower answers, respectively, gives a multiplicative gap search. If , the zero flow is already optimal. Otherwise, polynomial boundedness implies that the optimum is at least , while the elementary bound is at most . Searching to relative accuracy uses tests. This establishes Theorem 2.
Remark 1. In the introduction we claimed an efficient algorithm for families with efficient vertex separators via the work [7]. Note that adding the dummy edge does not cause a problem for such families: if is a vertex separator of size in the original graph, then is a separator of the augmented graph (also of size ).
Acknowledgements and declaration on the use of generative AI
During the preparation and revision of this manuscript, the author used ChatGPT and Codex by OpenAI as interactive research and writing tools. They were used to generate draft proof arguments, including initial drafts of the proofs of Theorems 3, 4, and 5, and to assist with literature searches, consistency checks, language editing, and presentation.
All research questions, algorithmic framework, and final mathematical arguments were developed and selected by the author. All AI-generated material was independently checked and substantially revised by the author; references and prior-work claims were verified against the cited sources. The author takes full responsibility for the correctness and content of the manuscript.
This work was in part motivated by interactions with Jack Spalding-Jamieson, during which the author learned about the existence of a (less efficient) reduction of M-MCF to min-cost flows.
References
- [1]Arora, Sanjeev, Elad Hazan, and Satyen Kale. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(6):121–164, 2012. https://doi.org/10.4086/toc.2012.v008a006.
- [2]Blanchard, Pierre, Desmond J. Higham, and Nicholas J. Higham. Accurate computation of the log-sum-exp and softmax functions. IMA Journal of Numerical Analysis, 41(4):2311–2330, 2021. https://doi.org/10.1093/imanum/draa038.
- [3]Carmon, Yair, John C. Duchi, Aaron Sidford, and Kevin Tian. A rank-1 sketch for matrix multiplicative weights. In Proceedings of the 32nd Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 589–623, 2019. https://proceedings.mlr.press/v99/carmon19a.html.arxiv.org/abs/1903.02675
- [4]Chen, Li, Andrei Graur, and Aaron Sidford. Accelerated approximate optimization of multicommodity flows on directed graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2203–2212, 2025. https://doi.org/10.1145/3711823.3718267.
- [5]Chen, Li, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. Journal of the ACM, 72(3):19:1–19:103, 2025. Conference version at FOCS 2022. https://doi.org/10.1145/3728631.
- [6]Diedrich, Florian and Klaus Jansen. An approximation algorithm for the general mixed packing and covering problem. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, volume 4614 of Lecture Notes in Computer Science, pages 128–139, 2007. https://doi.org/10.1007/978-3-540-74450-4_12.
- [7]Dong, Sally, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Guanghao Ye. Nested dissection meets IPMs: Planar min-cost flow in nearly-linear time. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 124–153, 2022. https://doi.org/10.1137/1.9781611977073.7.
- [8]Fleischer, Lisa K. Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics, 13(4):505–520, 2000. Conference version at FOCS 1999. https://doi.org/10.1137/S0895480199355754.
- [9]Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. Conference version at EuroCOLT 1995. https://doi.org/10.1006/jcss.1997.1504.
- [10]Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 300–309, 1998. https://doi.org/10.1109/SFCS.1998.743463.
- [11]Michael D. Grigoriadis and Leonid G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization, 4(1):86–107, 1994. https://doi.org/10.1137/0804004.
- [12]Michael D. Grigoriadis and Leonid G. Khachiyan. An exponential-function reduction method for block-angular convex programs. Networks, 26(2):59–68, 1995. https://doi.org/10.1002/net.3230260202.
- [13]Michael D. Grigoriadis and Leonid G. Khachiyan. Approximate minimum-cost multicommodity flows in Õ(ε−2KNM) time. Mathematical Programming, 75(3):477–482, 1996. Technical report published in 1995. https://doi.org/10.1007/BF02592195.
- [14]Michael D. Grigoriadis and Leonid G. Khachiyan. Coordination complexity of parallel price-directive decomposition. Mathematics of Operations Research, 21(2):321–340, 1996. https://doi.org/10.1287/moor.21.2.321.
- [15]Klaus Jansen. Approximation algorithm for the mixed fractional packing and covering problem. SIAM Journal on Optimization, 17(2):331–352, 2006. Conference version at IFIP TCS 2004. https://doi.org/10.1137/030601570.
- [16]Satyen Kale. Efficient Algorithms Using the Multiplicative Weights Update Method. PhD thesis, Princeton University, 2007. Technical Report TR-804-07. https://www.satyenkale.com/papers/thesis.pdf.
- [17]George Karakostas. Faster approximation schemes for fractional multicommodity flow problems. ACM Transactions on Algorithms, 4(1):13:1–13:17, 2008. Conference version at SODA 2002. https://doi.org/10.1145/1328911.1328924.
- [18]Philip Klein and Neal E. Young. On the number of iterations for Dantzig–Wolfe optimization and packing-covering approximation algorithms. SIAM Journal on Computing, 44(4):1154–1172, 2015. Conference version at IPCO 1999. https://doi.org/10.1137/12087222X.
- [19]Philip N. Klein, Serge A. Plotkin, Clifford Stein, and Éva Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23(3):466–487, 1994. Conference version at STOC 1990. https://doi.org/10.1137/S0097539792241175.
- [20]Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Éva Tardos, and Spyros Tragoudas. Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50(2):228–243, 1995. Conference version at STOC 1991. https://doi.org/10.1006/jcss.1995.1020.
- [21]Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994. Conference version at FOCS 1989. https://doi.org/10.1006/inco.1994.1009.
- [22]Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 121–130, 2010. https://doi.org/10.1145/1806689.1806708.
- [23]Cameron Musco, Christopher Musco, and Aaron Sidford. Stability of the Lanczos method for matrix function approximation. In Proceedings of the 29th Annual ACM–SIAM Symposium on Discrete Algorithms, pages 1605–1624, 2018. https://doi.org/10.1137/1.9781611975031.105.
- [24]Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the exponential, the Lanczos method and an Õ(m)-time spectral algorithm for balanced separator. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 1141–1160, 2012. https://doi.org/10.1145/2213977.2214080.
- [25]Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257–301, 1995. Conference version at FOCS 1991. https://doi.org/10.1287/moor.20.2.257.
- [26]Kent Quanrud. Nearly linear time approximations for mixed packing and covering problems without data structures or randomization. In Proceedings of the 2020 ACM–SIAM Symposium on Simplicity in Algorithms, pages 69–80, 2020. https://doi.org/10.1137/1.9781611976014.11.
- [27]Tomasz Radzik. Fast deterministic approximation for the multicommodity flow problem. Mathematical Programming, 78(1):43–58, 1997. Conference version at SODA 1995. https://doi.org/10.1007/BF02614505.
- [28]Farhad Shahrokhi and David W. Matula. The maximum concurrent flow problem. Journal of the ACM, 37(2):318–334, 1990. Conference version at the ACM Computer Science Conference 1987.DOI
- [29]Jonah Sherman. Area-convexity, ℓ∞ regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 452–460, 2017. https://doi.org/10.1145/3055399.3055501.
- [30]Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995–1018, 2005. https://www.jmlr.org/papers/v6/tsuda05a.html.DOI
- [31]Jorge Villavicencio and Michael D. Grigoriadis. Approximate structured optimization by cyclic block-coordinate descent. In Herbert Fischer, Bruno Riedmüller, and Stefan Schäffler, editors, Applied Mathematics and Parallel Computing: Festschrift for Klaus Ritter, pages 359–371. Physica-Verlag, Heidelberg, 1996. https://doi.org/10.1007/978-3-642-99789-1.
- [32]Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 538–546, 2001. https://doi.org/10.1109/SFCS.2001.959930.