%0 Journal Article %J Theoretical Computer Science %D 2011 %T Maximum bipartite flow in networks with adaptive channel width %A Azar,Yossi %A Mądry,Aleksander %A Moscibroda,Thomas %A Panigrahi,Debmalya %A Srinivasan, Aravind %K Adaptive channel width %K graph algorithm %K Linear program rounding %K Maximum flow %K Wireless networks %X Traditionally, network optimization problems assume that each link in the network has a fixed capacity. Recent research in wireless networking has shown that it is possible to design networks where the capacity of the links can be changed adaptively to suit the needs of specific applications. In particular, one gets a choice of having a few high capacity outgoing links or many low capacity ones at any node of the network. This motivates us to have a re-look at classical network optimization problems and design algorithms to solve them in this new framework. In particular, we consider the problem of maximum bipartite flow, which has been studied extensively in the fixed-capacity network model. One of the motivations for studying this problem arises from the need to maximize the throughput of an infrastructure wireless network comprising base-stations (one set of vertices in the bipartition) and clients (the other set of vertices in the bipartition). We show that this problem has a significantly different combinatorial structure in this new network model from the fixed-capacity one. While there are several polynomial time algorithms for the maximum bipartite flow problem in traditional networks, we show that the problem is NP-hard in the new model. In fact, our proof extends to showing that the problem is APX-hard. We complement our lower bound by giving two algorithms for solving the problem approximately. The first algorithm is deterministic and achieves an approximation factor of O ( log N ) , where N is the number of nodes in the network, while the second algorithm is randomized and achieves an approximation factor of e e − 1 . %B Theoretical Computer Science %V 412 %P 2577 - 2587 %8 2011/05/27/ %@ 0304-3975 %G eng %U http://www.sciencedirect.com/science/article/pii/S0304397510005852 %N 24 %R 10.1016/j.tcs.2010.10.023 %0 Conference Paper %B Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on %D 2005 %T Algorithmic graph minor theory: Decomposition, approximation, and coloring %A Demaine,E. D %A Hajiaghayi, Mohammad T. %A Kawarabayashi,K. %K algorithmic graph minor theory %K approximation algorithm %K combinatorial polylogarithmic approximation %K computational complexity %K constant-factor approximation %K graph algorithm %K graph coloring %K graph colouring %K half-integral multicommodity flow %K largest grid minor %K maximization problem %K minimization problem %K polynomial-time algorithm %K subexponential fixed-parameter algorithm %K topological graph theory %K treewidth %X At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor. %B Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on %P 637 - 646 %8 2005/// %G eng %R 10.1109/SFCS.2005.14