All types (
22 )
agt (
3 )
approximation (
5 )
Conference (
15 )
Journal (
10 )
network (
10 )
Preprint (
3 )
probability (
6 )

Sort by year:

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.

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”.

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.

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$).

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.