Faster and simpler algorithms for multicommodity flow and other fractional packing problems

By Naveen Garg, Jochen Könemann. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, methodology): “Multiplicative weight update (MWU) technique lies at the core of many learning algorithms [8], [19], [45], [20], [34].”
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “The oracle for this purpose is implemented using a variety of techniques: the multicommodity ﬂow algorithm of Garg and K¨onemann [29, 30] (and its subsequent improvement by Fleischer [24]), eigenvalue computations, and graph sparsiﬁcation algorithms of Bencz´ur and Karger [9] based on random…”
Expander flows, geometric embeddings and graph partitioning (2004, unknown): “, [26, 12]), which may be useful in practice.”
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs (2010, methodology): “The algorithm will employ the multiplicative weights update method, a framework established by Arora, Hazan, and Kale [3] to encompass proof techniques exploited in [16, 20, 10, 11].”
Expander flows, geometric embeddings and graph partitioning (2009, unknown): “, [26, 12]), which may be useful in practice.”
Tight approximation algorithms for maximum general assignment problems (2006, background): “2) can also be obtained via Lagrangian LP algorithms [11, 25, 33, 34].”
Maximizing the Lifetime of Wireless Sensor Networks with Mobile Sink in Delay-Tolerant Applications (2010, background): “The data generated by a source are sometimes called a commodity or a subflow [17], [18].”
Analysis of a local search heuristic for facility location problems (2000, background): “Recently, however, fully polynomial-time approximation schemes (FPTAS) have been derived for fractional packing/covering linear programs [10], which can be applied to certain uncapacitated facility location problems, as shown by Young [28] for 2”
A combinatorial, primal-dual approach to semidefinite programs (2007, methodology): “They eschew interior point methods in favor of more efficient (and combinatorial) Lagrangian relaxation methods; see Plotkin, Shmoys, Tardos [24], Young [30], Garg, Könemann [13], etc.”
Optimal hierarchical decompositions for congestion minimization in networks (2008, methodology): “There exists methods ([31], [26], [29], [18], [23]) for eﬃciently computing approximate solutions to such problems.”
Bandits with Knapsacks (2013, methodology): “Borrowing an idea from [30], [31], [32], we will use the multiplicatives weights update method to learn the optimal dual vector.”