Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(1)
multicommodity flow
Related Publications
(36)
Multicommodity maxflow mincut theorems and their use in designing approximation algorithms
Packing Directed Circuits Fractionally
PrimalDual Approximation Algorithms for Integral Flow and Multicut in Trees
An Approximate MaxFlow MinCut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms
Approximating Minimum Feedback Sets and Multicuts in Directed Graphs
Subscribe
Academic
Publications
Approximate maxflow min(multi)cut theorems and their applications
Approximate maxflow min(multi)cut theorems and their applications,10.1145/167088.167266,Naveen Garg,Vijay V. Vaziranit,Mihalis Yannakakis
Edit
Approximate maxflow min(multi)cut theorems and their applications
(
Citations: 159
)
BibTex

RIS

RefWorks
Download
Naveen Garg
,
Vijay V. Vaziranit
,
Mihalis Yannakakis
Consider the
multicommodity flow
problem in which the object is to maximize the sum of commodities routed. We prove the following approximate maxflow minmulticut theorem: min multicut O(log k)
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 698707, 1993
DOI:
10.1145/167088.167266
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
doi.acm.org
)
More »
Citation Context
(92)
...Given a graph, the interconnection of sources and destinations, linear programming [6], [5] and fast approximate solutions can be applied for solving singleor multicommodity flow maximization problems [
7
]...
Karl Martensson
,
et al.
Distributed resource management using iterative gradient update synthe...
...LP rounding algorithm of [
16
] yields an integral solution for the vertex multicut problem, whose cost is O(log n) times the cost of fractional solution...
V. S. Anil Kumar
,
et al.
Existence Theorems and Approximation Algorithms for Generalized Networ...
...of reducing the problem to the directed minimum capacity multicut problem in circular networks and of adapting the undirected sphere growing techniquedescribed in [
35
] to directed circular networks...
Paola Festa
,
et al.
Feedback Set Problems
...These results imply approximation algorithms for a variety of NPhard cut problems and give an approximation guarantee that is polylogarithmic in k as opposed to polylogarithmic in n. Garg, Vazirani and Yannakakis [
9
] proved that the mincut maxflow ratio for maximum multicommodity flow is also O(logk)...
Ankur Moitra
.
Approximation Algorithms for MulticommodityType Problems with Guarant...
...graphs [
12
] (where k is the number of sourcesink pairs), and a factor of 2 in trees [13]...
...know that ρ are O(log k) [
12
], 1.3438 [16], and 2 [21], respectively...
Peng Zhang
,
et al.
Approximation and Hardness Results for Label Cut and Related Problems
References
(18)
LeightonRao might be practical: faster approximation algorithms for concurrent flow with uniform capacities
(
Citations: 21
)
Philip N. Klein
,
Clifford Stein
,
Éva Tardos
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 310321, 1990
Excluded minors, network decomposition, and multicommodity flow
(
Citations: 121
)
Philip N. Klein
,
Serge A. Plotkint
,
Satish Rao
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 682690, 1993
Improved Bounds for the MaxFlow MinMulticut Ratio for Planar and K_r, rFree Graphs
(
Citations: 29
)
Éva Tardos
,
Vijay V. Vazirani
Journal:
Information Processing Letters  IPL
, vol. 47, no. 2, pp. 7780, 1993
The complexity of multiway cuts (extended abstract)
(
Citations: 29
)
Elias Dahlhaus
,
David S. Johnson
,
Christos H. Papadimitriou
,
Paul D. Seymour
,
Mihalis Yannakakis
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 241251, 1992
Proof Verification and Hardness of Approximation Problems
(
Citations: 773
)
Sanjeev Arora
,
Carsten Lund
,
Rajeev Motwani
,
Madhu Sudan
,
Mario Szegedyl
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 1423, 1992
Sort by:
Citations
(159)
A Unified Approach to Approximating Partial Covering Problems
(
Citations: 1
)
Jochen Könemann
,
Ojas Parekh
,
Danny Segev
Journal:
Algorithmica
, vol. 59, no. 4, pp. 489509, 2011
Approximation Algorithms for
Brian C. Dean
,
Adam Griffis
,
Ojas Parekh
,
Adam A. Whitley
Journal:
Algorithmica
, vol. 59, no. 1, pp. 8193, 2011
Approximation and hardness results for label cut and related problems
Peng Zhang
,
Jinyi Cai
,
LinQing Tang
,
WenBo Zhao
Journal:
Journal of Combinatorial Optimization  JCO
, vol. 21, no. 2, pp. 192208, 2011
Distributed resource management using iterative gradient update synthesis
Karl Martensson
,
Vladimeros Vladimerou
Published in 2011.
Better vaccination strategies for better people
(
Citations: 3
)
PoAn Chen
,
Mary David
,
David Kempe
Conference:
ACM Conference on Electronic Commerce  EC
, pp. 179188, 2010