On the max-flow min-cut ratio for directed multicommodity flows

Theoretical Computer SciencePublished 10 November 2005Open access

Mohammad Taghi Hajiaghayi, Tom Leighton

DOI10.1016/j.tcs.2005.10.037

Citations14

TL;DR

A pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows has applications in improving the approximation factor of the greedy algorithm for the maximum edge disjoint path problem.

Abstract

We present a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. In addition, this combinatorial problem has applications in improving the approximation factor of the greedy algorithm for the maximum edge disjoint path problem. More precisely, our upper bound improves the approximation factor for this problem to O(n3/4).

Keywords

Computer Science

ACM SIGACT NewsApproximation Algorithms for NP-Hard Problems

3,133 Citations1997Dorit S. Hochba

This book reviews the design techniques for approximation algorithms and the developments in this area since its inception about three decades ago and the "closeness" to optimum that is achievable in polynomial time.

View PDF

Journal of the ACMMulticommodity max-flow min-cut theorems and their use in designing approximation algorithms

813 Citations1999Tom Leighton, Satish Rao

This paper establishes max-flow min-cut theorems for several important classes of multicommodity flow problems and uses the result to design the first polynomial-time (polylog n-times-optimal) approximation algorithms for well-known NP-hard optimization problems.

View PDF

COMBINATORICAA Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

547 Citations2001Kamal Jain

Journal of Computer and System SciencesNear-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

140 Citations2003Venkatesan Guruswami, Sanjeev Khanna +3 more

Cut problems and their application to divide-and-conquer

109 Citations1996David B. Shmoys

This chapter will present approximation algorithms for several NP - hard graph-theoretic cut problems, and their subsequent application as a tool for the “divide” part of divide-and-conquer approximation algorithms for a wide variety of problems.

Improved results for directed multicut

56 Citations2003Anupam Gupta

A simple algorithm is given for the Minimum Directed Multicut problem, and it is shown that it gives an O(√n)-approximation, which improves on the previous approximation guarantee of Cheriyan, Karloff and Rabani.

Graph decomposition and a greedy algorithm for edge-disjoint paths

39 Citations2004Kasturi Varadarajan, Ganesh Venkataraman

The main result of this paper is the following theorem: All graphs that the paper deals with are directed with unit edge costs unless otherwise specified.

COMBINATORICAApproximating Directed Multicuts

37 Citations2005Joseph Cheriyan, Howard Karloff +1 more

COMBINATORICAA Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

33 Citations2004Michael J. Saks, Alex Samorodnitsky +1 more

For each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k, showing that for directed graphs, the trivial upper bound of k can not be improved.