Publications
This is the continuation of a paper originally released in 2019 as Beyond Submodular Maximization. In this paper our focus is more on discrete (as opposed to continuous) problems arising from classes of set functions which include submodular functions.
In multicommodity network flows, a supply-demand graph pair (G, H) (called a multiflow topology) is cut-sufficient if, for all capacity weights u and demand weights d, the cut condition is enough to guarantee the existence of a feasible multiflow. We characterize the cut-sufficient topologies for two classes of directed 2-commodity flows: roundtrip demands, where H is a 2-cycle, and 2-path demands, where H is a directed path of length two. To do so, we introduce a theory of relevant minors. Unlike the undirected setting, for directed graphs the cut-sufficient topologies are not closed under taking minors. They are however closed under taking relevant minors. Respectively, the cut-sufficient topologies for roundtrip and two-path demands are characterized by one and two forbidden relevant minors. As an application of our results, we show that recognizing cut-sufficiency for directed multiflow topologies is NP-hard, even for roundtrip demands. This is in contrast to undirected 2-commodity flows, for which topologies are always cut-sufficient.
We introduce a natural knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs.
Gomory-Hu (GH) Trees are a classical sparsification technique for graph connectivity. It is one of the fundamental models in combinatorial optimization which also continually finds new applications, most recently in social network analysis. For any edge-capacitated undirected graph $G=(V,E)$ and any subset of {\em terminals} $Z \subseteq V$, a Gomory-Hu Tree is an edge-capacitated tree $T=(Z,E(T))$ such that for every $u,v \in Z$, the value of the minimum capacity $uv$ cut in $G$ is the same as in $T$. Moreover, the minimum cuts in $T$ directly identify (in a certain way) those in $G$. It is well-known that we may not always find a GH tree which is a subgraph of $G$. For instance, every GH tree for the vertices of $K_{3,3}$ is a $5$-star. We characterize those graph and terminal pairs $(G,Z)$ which always admit such a tree. We show that these are the graphs which have no \emph{terminal-$K_{2,3}$ minor}. That is, no $K_{2,3}$ minor whose vertices correspond to terminals in $Z$. We also show that the family of pairs $(G,Z)$ which forbid such $K_{2,3}$ ``$Z$-minors'' arises, roughly speaking, from so-called Okamura-Seymour instances. More precisely, they are subgraphs of {\em $Z$-webs}. A $Z$-web is built from planar graphs with one outside face which contains all the terminals and each inner face is a triangle which may contain an arbitrary graph. This characterization yields an additional consequence for multiflow problems. Fix a graph $G$ and a subset $Z \subseteq V(G)$ of terminals. Call $(G,Z)$ {\em cut-sufficient} if the cut condition is sufficient to characterize the existence of a multiflow for any demands between vertices in $Z$, and any edge capacities on $G$. Then $(G,Z)$ is cut-sufficient if and only if it is terminal-$K_{2,3}$ free.
For any outerplanar graph we show there is capacitated tree which approximates every cut within a constant factor. We use this to find a constant-factor approximation to maximum weight disjoint paths (without congestion) in such graphs.
This is the first half of a paper originally released in 2019 as Beyond Submodular Maximization
Policy makers focus on stable strategies as the ones adopted by rational players. If there are many stable solutions, however, an important secondary question is how to select amongst them. We study this question for the multicommodity flow coalition game, introduced by Papadimitriou to model incentives and cooperation between autonomous systems in the Internet. In short, the strategies of the game are flows in a capacitated network (the supply graph). The payoff to any node is the total flow which it terminates. Markakis and Saberi show that this game is balanced and hence has a non-empty core by Scarf's Theorem. In the transferable utility (TU) version this also leads to a polynomial-time algorithm to find core elements but for the application to autonomous systems, side payments are not natural. Finding core elements in NTU games, however, tends to be computationally much more difficult. Even for this multiflow game, the only previous result is due to Yamada and Karasawa who give a procedure to find a core element when the supply graph is a path. We extend their work by designing an algorithm, called Incorporate, which produces many different core elements. We use our algorithm to evaluate several specific instances by running Incorporate to generate multiple core vectors. We call these the empirical core of the game. We find that sampled core vectors are more consistent with respect to social welfare (SW) than for fairness (minimum payout). For SW they tend to do as well as the optimal linear program value. In contrast, there is a larger range across fairness in the empirical core; the fairness values tend to be worse than the optimal fairness LP value. We study this discrepancy in the setting of general graphs with single-sink demands. We give an algorithm which produces core vectors that simultaneously maximize SW and fairness. This leads to the following bicriteria result for general games.Given any core-producing algorithm and any $lambda in (0,1)$, one can produce an approximate core vector with fairness (resp. social welfare) at least the optimal LP values.
Garg Vazarani and Yannakakis showed that the integrality gap for (the natural LP relaxation of) maximum disjoint paths (MEDP) in planar graphs is . Noting that their gap example (the grid) all but disappears if edge congestion 2 is allowed, Kleinberg and Tardos asked if MEDP in planar graphs behaves better when one admits constant congestion. A sequence of results ultimately showed that with constant (in fact 4) congestion, the integrality gap is O(1). Building on this result, we give a tight bound in terms of congestion. That is, if edge capacities in a planar graph are at least 2, then the integrality gap for MEDP is constant.
We show that the maximum single-sink unsplittable (or priority or confluent) flow problem is ``polynomial hard'' if the no-bottleneck assumption (NBA) is not satisfied. This holds even if all demands must lie in a range [1,1+ε] for some ε>0. This is quite sharp since if all demands are 1, this becomes a maximum flow problem. We then show that single-sink confluent flows are inapproximable to within a polylog factor even if the NBA holds.
A scheme is proposed to protect client virtual machines from being "attacked" by malicious VMs who try to co-locate on the same server.
The well-known grid example of Garg-Vazriani-Yannakakis shows that the integrality gap for the natural LP formulation of the undirected maximum edge-disjoint paths problem is $\Omega(\sqrt{n})$ even in planar graphs. Chekuri, Khanna and Shepherd established that a constant factor gap hols in planar graphs if edge-congestion $4$ is allowed. It is natural to ask for which classes of graphs does such a constant-factor constant-congestion hold. Its easy to deduce that for given constant bounds on the approximation and congestion, the class of ``nice'' graphs is minor-closed. Is the converse true? Does every minor-closed class exhibit such a constant factor/congestion bound relative to the LP formulation? One stumbling block for this problem is the fact that such bounds were not known for bounded treewidth graphs. In this paper we give a polytime algorithm which takes a fractional routing solution in a bounded treewidth graph and is able to integrally route (with congestion 1!) a constant fraction of the LP solution's value. This is the only such congestion 1 result known (apart from trees). The arguments also work for $k$-sums of graphs in some family, as long as the graph family has a constant factor/congestion bound. We use this to obtain such bounds hold for the class of $k$-sums of bounded genus graphs.
We resolve the longstanding gap on the competitive ratio for d-dimensional online vector bin packing (VBP). The best lower bound was 2 compared with the best upper bound of d+.7. When the bin sizes B are 1, we use a lower bound for online colouring (Halldorosson and Szegedy, 1992) and an idea of preparing'' for future adjacencies to easily get a lower bound. This is boosted to using an idea from (Dean-Goemans-Vondrak, 2005) in their work on approximability of stochastic packing integer programs. The lower bounds are more intricate in the cases when . We give almost matching upper bounds of in that case.
We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on designing the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). This model may be too conservative if additional information on traffic patterns is available. Another extreme is the fixed demand model, where one designs the network to support peak point-to-point demands. We introduce a capped hose model to explore a broader range of traffic matrices which includes the above two as special cases. It is known that optimal designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We shed light on the wider space of capped hose matrices, in order to see which traffic models are more shortest path-like as opposed to hub-like. In order to address the space in between, we use hierarchical multi-hub routing templates, a generalization of hub and tree routing. In particular, we show that by adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective. This initiates the study of a class of robust network design ($\rnd$) problems restricted to these templates. Our empirical analysis is based on a heuristic for this new hierarchical $\rnd$ problem. We also propose that it is possible to define a routing indicator that accounts for the strengths of the marginals and peak demands and use this information to choose the appropriate routing template. We benchmark our approach against other well-known routing templates, using representative carrier networks and a variety of different capped hose traffic demands, parameterized by the relative importance of their marginals as opposed to their point-to-point peak demands. This study also reveals conditions under which multi-hub routing gives improvements over single-hub and shortest-path routings.
We want to build a network that can transport any demand matrix where . The 's are called marginals - they simply indicate that the total demand (traffic) involving node is at most . The class of all such matrices are called the hose matrices. We dont know or care who will actually communicate with. In addition, we must route traffic "obliviously", which means that routing of traffic between nodes and does not depend on what other traffic there is in the network. In other words, our routing cannot adapt to congestion in the network: we must prespecify how any pair communicates regardless of which hose demand matrix we are given. Our goal is to find an oblivious routing such that the total capacity needed on the edges of the network is minimized. This is called the Virtual Private Network (VPN) problem. Fingerhut-Suri-Turner and Gupta-Kleinberg-Kumar-Rastogi-Yener showed that there is always a tree network whose total cost is within a factor of 2 of the minimum cost VPN. It was widely speculated and conjectured in Italiano-Leonardi-Oriolo, that there is always an optimal VPN which is a tree. We show this is true using pyramidal routing, a concept recently introduced by Grandoni-Kaibel-Oriolo-Skutella to attack the VPN problem.
The maximum edge-disjoint path problem (EDP) consist of a supply graph and some terminal pairs for . The goal is to find a maximum subset of the pairs that can be simultaneously satisfied by disjoint paths in the supply graph. Guruswami et al. (see below) showed that in directed graphs the maximum edge-disjoint path problem (EDP) is hard to polytime approximate to better than a factor of (where m is the number arcs and any ). However similar hardness results were not known for the undirected version (it was only known to be hard to constant approximate). This paper studies a relaxation of EDP in undirected graphs, the all-or-nothing multicommodity flow problem, where one is only asked to find a subset of the pairs for which there is a flow satisfying their demands. The main result is that the integrality gap for this relaxation is at most a polylogarithmic factor (thus exponentially better than for directed graphs). Recently an almost matching polylogarithmic lower bound was found by Andrews and Zhang.
We study a detailed model for virtual machine migration in tree (or near tree) topologies. Our algorithms lead to scalable heuristics with promising empirical results on a large topology.
We show for the first time a class of (separable) demand polytopes for which the associated robust network design problem exhibits polylog hardness. We also show that for the class of demand polytopes induced by a tree (T-topes) there is an 8-approximate polytime algorithm (though this class of problems may possibly be in P).
Consider the robust network design problem of finding a minimum cost network with enough capacity to route all traffic demand matrices in a given polytope. We investigate the impact of different routing models in this robust setting: in particular, we compare \emph{oblivious} routing, where the routing between each terminal pair must be fixed in advance, to \emph{dynamic} routing, where routings may depend arbitrarily on the current demand. Our main result is a construction that shows that the optimal cost of such a network based on oblivious routing (fractional or integral) may be a factor of more than the cost required when using dynamic routing. This is true even in the important special case of the asymmetric hose model. This answers a question in \cite{chekurisurvey07}, and is tight up to constant factors. Our proof technique builds on a connection between expander graphs and robust design for single-sink traffic patterns~\cite{ChekuriHardness07}.
In recent years, several new models for network flofws have been analyzed, inspired by emerging telecommunication technologies. These include models of {\em resilient flow}, motivated by the introduction of high capacity optical links, {\em coloured flow}, motivated by Wavelength-Division-Multiplexed optical networks, {\em unsplittable flow} motivated by SONET networks, and {\em confluent flow} motivated by next-hop routing in internet protocol (IP) networks. In each model, the introduction of new side-constraints means that a max-flow min-cut theorem does not necessarily hold, even in the setting where all demands are destined to a common node (sink) in the network. In such cases, one may seek bounds on the flow-cut gap'' for the model. Such approximate max-flow min-cut theorems are a useful measure for bounding the impact of new technology on congestion in networks whose traffic flows obey these side constraints.
For planar graphs, we show that if each edge capacity is at least 4, then the natural LP for the maximum integral multicommodity flow problem has a constant integrality gap (as opposed to if capacities are at most ).
We consider the single sink multicommodity flow problem where flow out of any node may use at most arcs. If , then such flows are called confluent; if we call such flows bifurcated. It was previously shown that confluent flows may have node congestion up to . We show that for , this unbounded congestion gap disappears: we show that the congestion gap is at most 2 (and this is best possible). In order to better understand the trade-off between and , we consider the -confluent flow problem for . Here we require that a fraction of the flow out of any node must exit on a single arc (and the remainder on possibly one other arc). We show that for any , there is a -confluent flow of congestion at most .
We study problems related to the design of transparent optical networks, where flow paths must also be assigned an end to end'' wavelength (colour). If, this is impossible, an expensive (OEO) conversion takes place. We try to partition the edges of a graph into transparent islands so that no demand has to hop between islands too often. In a different version, we show a simple fractional implies integral result for single source multicommodity multicoloured flow. This reduces the corresponding WDM network design problem to a single-source buy at bulk problem with single cable type, for which a 3.55 approximation is known (Hassin, Ravi, Salman).
We are given an uncapacitated undirected graph and a collection of matrices for pairwise traffic demands between nodes of . What is the cheapest assignment of edge capacity needed so that any matrix in can be routed using this capacity? In the "oblivious routing" setting, for each pair there is a pre-specified unit flow ("template") and one may only scale this flow up or down according to the value of . In this version Applegate and Cohen showed that the optimal capacity is computable in polytime. If we may choose our flows dynamically for each different demand matrix, then obviously we may need less capacity. We show, by a reduction from graph expansion, that this problem is hard, even for a single-source hose problem (and even to get within a factor 2).
Garg, Vazarani and Yannakakis showed examples where the integrality gap (the natural formulation) for the maximum edge disjoint path problem (EDP) is as bad as even for planar graphs. For planar graphs, we show that if each edge capacity is at least 2, then this integrality gap drops to log(n).
We introduce the following problem. Given a graph where each node has a capacity , and we are also given a set of edges where each such also comes with an integer demand and weight . A subset of is a demand matching if for each node, the total demand of -edges incident to it is at most . We study the natural IP formulation for this (NP hard) problem and find that its integrality gap lies between 2.5 and 3 for bipartite graphs, and between 3 and 3.5 for general graphs.
Network design problems arising from supermodular set requirement functions have been well studied, as have orientation problems where one wishes to orient some undirected edges to satisfy some connectivity conditions. Motivated by the design of strongly connected networks, we consider (for the first time as far as we know) the problem of joint orientation and subset selection of edges/arcs. The main finding is that a classical result of Frank on intersecting supermodular functions extends very simply to the joint setting.
Decompositions are described for visualizing when a set of arcs forms a dijoin. An elementary algorithm is given for finding a mincost dijoin that runs in O(n^2m) - matching the best running time due to Gabow. A number of questions are posed related to packing dijoins. One of these is that there exists a constant such that in any weighted digraph whose minimum weight directed cut is of size , there is a packing of dijoins (into the weights). It is proved there is a half-integral such packing.
We consider the multicommodity all-or-nothing flow problem in a tree. We are given a tree with integer edge capacities and a set of demand edges , each with an integer . A subset of demands is routable if no edge capacity is violated after each demand sends units of flow between its endpoints. Special cases of this problem include when the tree is a single edge (knapsack problem), when the tree is a star (demand matching problem) and when all demands are 1 (integer multicommodity flow on a tree), or when the tree is a line (interval packing), and when the tree is a star (the b-matching problem). For the unit demand case, Garg, Vazarani and Yannakis gave a 2-approximation for the the maximum cardinality problem. We show that the integrality gap for the weighted (unit demand) case is at most 4. Following, Cheriyan, Jordan, and Ravi, we ask whether this can be brought down to 3/2 (thus generalizing Shannon's multigraph edge colouring result). Our result together with a technique of Kolliopoulos and Stein can then be used to show that for general demands, a gap of at most 48 holds (the first constant factor for this problem).
The main new result in this paper is a polytime algorithm to determine whether a graph is partitionable: i.e., for each node v, G-v is -colourable and -clique-coverable, where (resp. ) is the size of a max stable set (resp. clique). We then speculate whether separation routines for partitionable inequalities could be practical for solving packing problem instances for dense matrices?
These papers provide a formal study of the border gateway protocol (BGP) which has become the defacto standard for determining routes between different autonomous systems (i.e. organizations, or enterprises under a common administrative control). Within an AS, protocols based on finding shortest paths are used for route selection, and hence, like the Ford-Bellman algorithm, they are guaranteed to finally stabilize into shortest path trees to each destination. The same is not true for BGP since the nodes may order preferences on paths arbitrarily. The SIGCOMM paper proposes a change to the protocol which provably eliminates one of the reasons for instability observed in practice (due to MED attribute). The solution was presented to the IETF.
Many coarse network designs are performed as follows. For each source-destination pair of nodes with say traffic demand between them, reserve units of capacity on each link of a shortest path in the network (topology). This reserved bandwidth is completely vulnerable, however, to any single link failure. This paper generalizes the shortest path problem to natural resilient path analogues. Several resilient (up to failures) versions are discussed including the case where we must route traffic on a collection of disjoint paths. Here a simple algorithm is described for the fractional version, and a -approximation algorithm is described for the integer version. It is also shown that it is NP-hard to obtain a polytime )-approximation algorithm, for any . The longer version contains more discussion of alternative network resilience and restoration strategies.
It is shown how a couple of augmentation rules can be used to turn a multicommodity flow on a ring (cycle graph) into a minimum cost such flow. Such combinatorial algorithms for exact minimum cost multicommodity do not seem to exist, even in simple cases.
It is shown that finding the maximum number of a given set of pairs that can be connected by arc-disjoint paths in a directed graph cannot be approximated (in polytime) even within a factor of for any . On the positive side, we describe a factor approximation achievable by a greedy algorithm even in the presence of arc capacities (a greedy such approximation was already known for unit capacities).
Originally motivated by routing in a passive optical ring network, we consider the multicommodity flow problem in a node-capacitated ring. The cut condition is not sufficient to characterize solvability of such instances. We show, however, that it is sufficient to consider distance cut inequalities induced by node weights. We also see that a fractionally routable set of demands can be integrally routed if we increase each node capacity by .
Given a matrix with two per row, when is it the case that the Chvatal closure of the polytope gives an integer polytope? This happens precisely when the rows of determine a so-called t-perfect graph. No characterization of these graphs/matrices is known. This paper characterizes those graphs for which every subgraph is t-perfect. This extends earlier results on graphs with no minor. Schrijver has since shown that the linear system for this class of graphs is also TDI (totaly dual integral).
These two papers (the first empirical, the latter theoretical) argue that the cost of wavelength converters in a wavelength division multiplexed (WDM) network, is not warranted in static networks with large fiber capacities (represented as many parallel edges). Also discussed, is the phenomenon that colouring random instances of path intersection graphs is much easier in practice than colouring random instances of graphs.
We describe a decomposition for cubic graphs that contain no minor isomorphic to the Petersen Graph with one edge removed. This is used to show such graphs are 3-edge-colourable.
It is seen how a more general form of Lehman's theorem (only stated in Lehman's own paper on the topic, but whose proof follows directly from the Seymour and Padberg presentations) can be translated to obtain results for packing problems. In particular, this leads to a complete characterization of the stable set polytope for graphs , such that is bipartite for each node .
A graph is -critical if it is not -node colourable, but every proper subgraph is. Toft conjectured (197?) that every such graph had a subgraph which is obtained from by subdividing each edge an even number of times. This conjecture could be viewed as the natural analogue to the fact that is bipartite only if it has no odd cycle. We prove the conjecture in the case where such a graph has a node of degree (this was the first partial result).
Even, Itai and Shamir showed that in undirected graphs the following -terminal edge-disjoint path (EDP) problem is NP-hard: do there exist edge-disjoint paths, of which join terminals , and of which join terminals ? A main consequence of this paper is that this problem is solvable for graphs on a fixed surface.
Schrijver gave a polytime method for determining the existence of disjoint paths between terminal pairs for graphs embedded on a fixed surface and for fixed . Schrijver's approach is to consider each homotopic pattern that the possible collections of disjoint paths may form. For each pattern, he then applies shifting techniques to see whether there is a solution to the problem. The number of homotopies required ostensibly grows exponentially (thus the reason for a fixed ). We show that even for non-fixed , one may restrict to a polynomially bounded (in the size of the supply and demand graphs) number of homotopic patterns as long as the number of terminals is fixed.
An algorithm is given to determine for a given planar graph and nodes s,t, the maximum number of s-t paths such that there is no edge joining internal nodes on distinct paths in the collection. For graphs on a fixed surface, and with fixed, an algorithm is described to determine whether there exists such a collection of paths. The fixed assumption can be dropped by applying the results from "Preselecting..." above.
Martin Grotschel in the early 1980's posed the following as one of the top outstanding questions in polyhedral combinatorics. Find a complete description for the stable set polytope of a claw-free graph (there is no stable set of size in for each ). As every line graph is claw-free, such a system would generalize Edmonds Mathching Polyhedron Theorem. Despite attempts by many, such a result remains elusive. In this paper a description, and compact formulation, is given for graphs where for each there is no stable set of size amongst the nodes at distance from (called distance claw-free). This problem was solved in 2005! The solution came about from the work of Seymour-Chudnovsky and Eisenbrand-Oriolo-Stauffer-Ventura. It turned out that distance claw-free graphs formed a critical subclass in the solution.