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 CompComm 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 amulticommodity 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/log n) -approximation algorithm 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.
The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case
SCUTELLA', MARIA GRAZIA
2008-01-01
Abstract
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 CompComm 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 amulticommodity 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/log n) -approximation algorithm 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
