Premium
The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case
Author(s) -
Scutellà Maria G.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20205
Subject(s) - maximum flow problem , mathematics , multi commodity flow problem , flow network , approximation algorithm , minimum cut , maximum cut , mathematical optimization , robust optimization , flow (mathematics) , minimum cost flow problem , set (abstract data type) , optimization problem , time complexity , polynomial , cutting plane method , computer science , combinatorics , integer programming , graph , mathematical analysis , geometry , programming language
We study an optimization problem which can be interesting in several network applications, especially in telecommunication. Given a capacitated directed network G in which a flow, related to a certain commodity, has to be sent from a given set of origins to a given set of destinations, we want to compute a maximum congested cut, i.e., a cut ( S , T ) of G which maximizes the ratio between the net demand of T and the capacity of the cut. We will show that a maximum congested cut can be computed in polynomial time by formulating the problem as a special maximum mean‐weight cut problem, and solving it by Newton's method for linear fractional combinatorial optimization (Radzik, Complexity in Numerical Optimization, World Scientific, Singapore, 1993). The introduced formulation will be extended to the case in which the flow demands vary in a polyhedron D , and a cut has to be determined which maximizes the congestion with respect to the flow demands in D , addressing a robust version of the problem. We will prove that the robust maximum congested cut problem is coNP‐Hard. Special cases solvable in polynomial time as well as approximation algorithms for some relevant hard cases will be proposed. The specialization of the proposed approaches to the well‐studied class of Hose models (Duffield et al., Proc., Conf Appl Technol Architect Protocol Comp Comm 29 (1999), 95–108) will be discussed. Then, in the second part of the paper, we will investigate the case in which k commodities are given, and a maximum congested cut has to be computed in such a multicommodity flow context. This problem is NP‐Hard. Some algorithmic considerations will be formulated in order to approximate the maximum congested cut in multicommodity networks, also addressing the robust version of the problem. A consequence of the stated results is a polynomial time algorithm for the sparsest cut problem in undirected graphs, for the special case in which k is O (log n ), and an O ( ${{k}\over{\log n}}$ )‐approximationalgorithm for the general case, where n denotes the cardinality of the node set. Furthermore, a new heuristic approach for the directed sparsest cut problem will be suggested. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008