Sort by year:

Accepted to SODA

We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given in [Végh 2016]; our new algorithm is much simpler, and much faster. The complexity bound $O((m+n\log n)mn\log (n^2/m))$ improves on the previous estimate in [ Végh 2016] by almost a factor $O(n^2)$. Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.

The bottleneck of the currently best (ln(4) + epsilon)-approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known. In this paper, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with 3 Steiner neighbors. This implies faster ln(4)-approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.

Let $T$ be an infinite rooted tree with weights $w_e$ assigned to its edges. Denote by $m_n(T)$ the minimum weight of a path from the root to a node of the $n$th generation. We consider the possible behaviour of $m_n(T)$ with focus on the two following cases: we say $T$ is explosive if \[ \lim_{n\to \infty}m_n(T) < \infty, \] and say that $T$ exhibits linear growth if \[ \liminf_{n\to \infty} \frac{m_n(T)}{n} > 0. \]

We consider a class of infinite randomly weighted trees related to the Poisson-weighted infinite tree, and determine precisely which trees in this class have linear growth almost surely. We then apply this characterization to obtain new results concerning the event of explosion in infinite randomly weighted spherically-symmetric trees, answering a question of Pemantle and Peres. As a further application, we consider the random real tree generated by attaching sticks of deterministic decreasing lengths, and determine for which sequences of lengths the tree has finite height almost surely.

Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. The notion of “hierarchical hubbing” was introduced (in the narrow context of a specific robust network design question), by Olver and Shepherd [2010]. Hierarchical hubbing allows for routings with a multiplicity of “hubs” which are connected to the terminals and to each other in a treelike fashion. Recently, Fréchette et al. [2013] explored this notion much more generally, focusing on its applicability to an extension of the well-studied hose model that allows for upper bounds on individual point-to-point demands. In this paper, we consider hierarchical hubbing in the context of a previously studied (and extremely natural) generalization of the hose model, and prove that the optimal hierarchical hubbing solution can be found efficiently. This result is relevant to a recently proposed generalization of the “VPN Conjecture”.

Motivated by the recent emergence of the so-called opportunistic communication networks, we consider the issue of adaptivity in the most basic continuous time (asynchronous) rumor spreading process. In our setting a rumor has to be spread to a population; the service provider can push it at any time to any node in the network and has unit cost for doing this. On the other hand, as usual in rumor spreading, nodes share the rumor upon meeting and this imposes no cost on the service provider. Rather than fixing a budget on the number of pushes, we consider the cost version of the problem with a fixed deadline and ask for a minimum cost strategy that spreads the rumor to every node. A non-adaptive strategy can only intervene at the beginning and at the end, while an adaptive strategy has full knowledge and intervention capabilities. Our main result is that in the homogeneous case (where every pair of nodes randomly meet at the same rate) the benefit of adaptivity is bounded by a constant. This requires a subtle analysis of the underlying random process that is of interest in its own right.

Game Theory and Mechanism Design are by now standard tools for studying and designing massive decentralized systems. Unfortunately, designing mechanisms that induce socially efficient outcomes often requires full information and prohibitively large computational resources. In this work we study simple mechanisms that require only *local* information. Specifically, in the setting of a classic scheduling problem, we demonstrate local mechanisms that induce outcomes with social cost close to that of the socially optimal solution. Somewhat counter-intuitively, we find that mechanisms yielding Pareto dominated outcomes may in fact enhance the overall performance of the system, and we provide a justification of these results by interpreting these inefficiencies as externalities being internalized. We also show how to employ randomization to obtain yet further improvements. Lastly, we use the game-theoretic insights gained to obtain a new combinatorial approximation algorithm for the underlying optimization problem.

Pipage rounding is a dependent random sampling technique that has several interesting properties and diverse applications.

One property that has been useful in applications is negative correlation of the resulting vector. There are some further properties that would be interesting to derive, but do not seem to follow from negative correlation. In particular, recent concentration results for sums of independent random matrices are not known to extend to a negatively dependent setting.

We introduce a simple but useful technique called *concavity of pessimistic estimators*. This technique allows us to show concentration of submodular functions and concentration of matrix sums under pipage rounding. The former result answers a question of Chekuri et al. (2009). To prove the latter result, we derive a new variant of Lieb’s celebrated concavity theorem in matrix analysis.

We provide numerous applications of these results. One is to *spectrally-thin trees*, a spectral analog of the *thin trees* that played a crucial role in the recent breakthrough on the asymmetric traveling salesman problem. We show a polynomial time algorithm that, given a graph where every edge has effective conductance at least $\kappa$, returns an $O(\kappa^{-1} \cdot \log n / \log \log n)$-spectrally-thin tree. There are further applications to rounding of semidefinite programs and to a geometric question of extracting a nearly-orthonormal basis from an isotropic distribution.

We consider robust network design problems where the set of feasible demands may be given by an arbitrary polytope or convex body more generally. This model, introduced by Ben-Ameur and Kerivin (2003), generalizes the well studied virtual private network (VPN) problem. Most research in this area has focused on ﬁnding constant factor approximations for speciﬁc polytope of demands, such as the class of hose matrices used in the deﬁnition of VPN. As pointed out in Chekuri (2007), however, the general problem was only known to be APX-hard (based on a reduction from the Steiner tree problem). We show that the general robust design is hard to approximate to within logarithmic factors. We establish this by showing a general reduction of buy-at-bulk network design to the robust network design problem. In the second part of the paper, we introduce a natural generalization of the VPN problem. In this model, the set of feasible demands is determined by a tree with edge capacities; a demand matrix is feasible if it can be routed on the tree. We give a constant factor approximation algorithm for this problem that achieves factor 8 in general, and 2 for the case where the tree has unit capacities.

We consider the following network design problem. We are given an undirected graph $G=(V,E)$ with edges costs $c(e)$ and a set of terminal nodes $W$. A *hose* demand matrix for $W$ is any symmetric matrix $[D_{ij}]$ such that for each $i$, $\sum_{j \neq i} D_{ij} \leq 1$. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An *oblivious routing* template, in this context, is a simple path $P_{ij}$ for each pair $i,j \in W$. Given such a template, if we are to route a demand matrix $D$, then for each $i,j$ we send $D_{ij}$ units of flow along each $P_{ij}$. Fingerhut et al. (1997) and Gupta et al. (2001) obtained a $2$-approximation for this problem, using a solution template in the form of a tree. It has been widely asked and subsequently conjectured that this solution actually results in the optimal capacity for the single path VPN design problem; this has become known as the *VPN conjecture*.

The conjecture has previously been proven for some restricted classes of graphs (Hurkens et al. 2005, Grandoni et al. 2007, Fiorini et al. 2007). Our main theorem establishes that this conjecture is true in general graphs. This proves that the single path VPN problem is solvable in polynomial time. We also show that the multipath version of the conjecture is false.

Consider a branching random walk on $\mathbb{R}$, with offspring distribution $Z$ and nonnegative displacement distribution W. We say that explosion occurs if an infinite number of particles may be found within a finite distance of the origin. In this paper, we investigate this phenomenon when the offspring distribution $Z$ is heavy-tailed. Under an appropriate condition, we are able to characterize the pairs $(Z, W)$ for which explosion occurs, by demonstrating the equivalence of explosion with a seemingly much weaker event: that the sum over generations of the minimum displacement in each generation is finite. Furthermore, we demonstrate that our condition on the tail is best possible for this equivalence to occur. We also investigate, under additional smoothness assumptions, the behavior of $M_n$, the position of the particle in generation $n$ closest to the origin, when explosion does not occur (and hence $\lim_{n\rightarrow\infty}M_n=\infty$).

We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being the problem of finding a spanning tree with degree constraints. Since the problem is hard, the goal is typically to find a spanning tree that violates the constraints as little as possible.

Iterative rounding became the tool of choice for constrained spanning tree problems. However, iterative rounding approaches are very hard to adapt to settings where an edge can be part of a super-constant number of constraints. We consider a natural constrained spanning tree problem of this type, namely where upper bounds are imposed on a family of cuts forming a chain. Our approach reduces the problem to a family of independent matroid intersection problems, leading to a spanning tree that violates each constraint by a factor of at most 9.

We also present strong hardness results: among other implications, these are the first to show, in the setting of a basic constrained spanning tree problem, a qualitative difference between what can be achieved when allowing multiplicative as opposed to additive constraint violations.

Until recently, LP relaxations have played a limited role in the design of approximation algorithms for the Steiner tree problem. In 2010, Byrka et al. presented a ln(4)+epsilon approximation based on a hypergraphic LP relaxation, but surprisingly, their analysis does not provide a matching bound on the integrality gap.

We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem – one that heavily exploits methods and results from the theory of matroids and submodular functions – which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, we present a deterministic ln(4)+epsilon approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap.

Similarly to Byrka et al., we iteratively fix one component and update the LP solution. However, whereas they solve an LP at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 bound on the integrality gap for quasi-bipartite graphs.

For the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, providing a fast independence oracle for our matroids.

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 *oblivious* routing, where the routing between each terminal pair must be fixed in advance, to *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 $\Omega(\log{n})$ 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 Chekuri (2007), 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 (Chekuri et al. 2007).

We consider a priority-based selﬁsh routing model, where agents may have diﬀerent priorities on a link. An agent with a higher priority on a link can traverse it with a smaller delay or cost than an agent with lower priority. This general framework can be used to model a number of diﬀerent problems. The structural properties that lead to ineﬃciencies in routing choices appear diﬀerent in this priority-based model compared to the classical model. In particular, in parallel link networks with nonatomic agents, the price of anarchy is exactly one in the priority-based model; that is, selﬁsh behaviour leads to optimal routings. In contrast, in the standard model the worst possible price of anarchy can be achieved in a simple two-link network. For multi-commodity networks, selﬁsh routing does lead to ineﬃciencies in the priority-based model. We present tight bounds on the price of anarchy for such networks. Speciﬁcally, in the nonatomic case the worst-case price of anarchy is exactly $(d + 1)^{d+1}$ for polynomial latency functions of degree $d$ (hence 4 for linear cost functions). For atomic games, the worst-case price of anarchy is exactly $3+2\sqrt{2}$ in the weighted case, and exactly 17/3 in the unweighted case. An upper bound of $O(2^dd^d)$ is also shown for polynomial cost functions in the atomic case, although this is not tight. Our framework (and results) also generalise to include models similar to congestion games.