Arrow Research search

Author name cluster

F. Bruce Shepherd

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
1 author row

Possible papers

19

SODA Conference 2021 Conference Paper

Beyond Submodular Maximization via One-Sided Smoothness

  • Mehrdad Ghadiri
  • Richard Santiago
  • F. Bruce Shepherd

The multilinear framework was developed to achieve the breakthrough 1 – 1/ e approximation for maximizing a monotone submodular function subject to a matroid constraint, which includes the submodular welfare problem as special case. This framework has a continuous optimization part (solving the multilinear extension of a submodular set function) and a rounding part (rounding a fractional solution to an integral one). We extend both parts so that the resulting generalized framework may be used on a wider array of problems. In particular, we make a conceptual contribution by identifying a family of parameterized functions and their applications. As a running example we focus on solving diversity problems max, where ℳ is matroid. These diversity functions have A ij ≥ 0 as a measure of dissimilarity of i, j, and A has 0-diagonal. This family of problems ranges from intractable problems such as densest k -subgraph, to ½-approximable metric diversity problems. The multilinear extension F of such diversity functions satisfies ▿ 2 F ( x ) = A ≥ 0 and hence the original multilinear framework (which assumes non-positive Hessians) does not directly apply. Instead we introduce a new parameter for functions F ∊ C 2 which measures the approximability of the associated problem max{ F ( x ): x ∊ P }, for solvable downwards-closed polytopes P. A function F is called one-sided σ-smooth if for all u, x ≥ 0, x = 0. For σ = 0 this class includes previously studied classes such as continuous DR-submodular functions, and much more. For the multlinear extension of a diversity function, we show that it is one-sided σ-smooth whenever A ij forms a σ-semi-metric. We give an Ω(1/σ)-approximation for the continuous maximization problem of monotone, normalized one-sided σ-smooth F with an additional property: non-positive third order partial derivatives. Since the multilinear extension of a diversity function has this additional property we can apply the extended multilinear framework to this family of discrete problems. This requires new matroid rounding techniques for quadratic objectives. The result is an Ω(1/σ 3/2 )-approximation for maximizing a σ-semi-metric diversity function subject to matroid constraint. This improves upon the previous best bound of Ω(1/σ) and we give evidence that it may be tight. For general one-sided smooth functions, we show the continuous process gives an Ω(1/3 2σ )-approximation, independent of n. In this setting, by discretizing, we present a concrete poly-time algorithm for multilinear functions that satisfy the one-sided σ-smoothness condition.

Details

ICML Conference 2019 Conference Paper

Multivariate Submodular Optimization

  • Richard Santiago
  • F. Bruce Shepherd

Submodular functions have found a wealth of new applications in data science and machine learning models in recent years. This has been coupled with many algorithmic advances in the area of submodular optimization: (SO) $\min/\max f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is a given family of feasible sets over a ground set $V$ and $f: 2^V \rightarrow \mathbb{R}$ is submodular. In this work we focus on a more general class of multivariate submodular optimization (MVSO) problems: $\min/\max f (S_1, S_2, \ldots, S_k): S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ to denote union of disjoint sets and hence this model is attractive where resources are being allocated across $k$ agents, who share a “joint” multivariate nonnegative objective $f(S_1, S_2, \ldots, S_k)$ that captures some type of submodularity (i. e. diminishing returns) property. We provide some explicit examples and potential applications for this new framework. For maximization, we show that practical algorithms such as accelerated greedy variants and distributed algorithms achieve good approximation guarantees for very general families (such as matroids and $p$-systems). For arbitrary families, we show that monotone (resp. nonmonotone) MVSO admits an $\alpha (1-1/e)$ (resp. $\alpha \cdot 0. 385$) approximation whenever monotone (resp. nonmonotone) SO admits an $\alpha$-approximation over the multilinear formulation. This substantially expands the family of tractable models. On the minimization side we give essentially optimal approximations in terms of the curvature of $f$.

Details

FOCS Conference 2015 Conference Paper

Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem

  • F. Bruce Shepherd
  • Adrian Vetta
  • Gordon T. Wilfong

A single-sink confluent flow is a routing of multiple demands to a sink r such that any flow exiting a node v must use a single arc. Hence, a confluent flow routes on a tree within the network. In uncapacitated (or uniform-capacity) networks, there is an O(1)-approximation algorithm for demand maximization and a logarithmic approximation algorithm for congestion minimization [6]. We study the case of capacitated networks, where each node v has its own capacity μ(v). Indeed, it was recently shown that demand maximization is in approximable to within polynomial factors in capacitated networks [20]. We circumvent this lower bound in two ways. First, we prove that there is a polylogarithmic approximation algorithm for demand maximization in networks that satisfy the ubiquitous no-bottleneck assumption (NBA). Second, we show a bicriteria result for capacitated networks without the NBA: there is a polylog factor approximation guarantee for demand maximization provided we allow congestion 2. We model the capacitated confluent flows problem using a multilayer linear programming formulation. At the heart of our approach for demand maximization is a rounding procedure for flows on multilayer networks which can be viewed as a proposal algorithm for an extension of stable matchings. In addition, the demand maximization algorithms require, as a subroutine, an algorithm for approximate congestion minimization in a special class of capacitated networks that may be of independent interest. Specifically, we present a polylogarithmic approximation algorithm for congestion minimization in monotonic networks - those networks with the property that μ(u) ≤ μ(v) for each arc (u, v).

Details

FOCS Conference 2011 Conference Paper

Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

  • Loïc Seguin-Charbonneau
  • F. Bruce Shepherd

We study the maximum edge-disjoint path problem (MEDP) in planar graphs. We are given a set of terminal pairs and wish to find a maximum routable subset of demands. That is, a subset of demands that can be connected by edge-disjoint paths. It is well-known that there is an integrality gap of order square root of the number of nodes for this problem even on a grid-like graph, and hence in planar graphs (Garg et al.). In contrast, Chekuri et al. show that for planar graphs, if LP is the optimal solution to the natural linear programming relaxation for MEDP, then there is a subset of size OPT over the logarithm of the number of nodes which is routable with congestion 2. Subsequently they showed that it is possible to get within a constant factor of the optimal solution with congestion 4 instead of 2. We strengthen this latter result to show that a constant approximation is possible also with congestion 2 (and this is tight via the integrality gap grid example). We use a basic framework from work by Chekuri et al. At the heart of their approach is a 2-phase algorithm that selects an Okamura-Seymour instance. Each of their phases incurs a factor 2 congestion. It is possible to reduce one of the phases to have congestion 1. In order to achieve an overall congestion 2, however, the two phases must share capacity more carefully. For the Phase 1 problem, we extract a problem called rooted clustering that appears to be an interesting problem class in itself.

Details

STOC Conference 2008 Conference Paper

The vpn conjecture is true

  • Navin Goyal
  • Neil Olver
  • F. Bruce Shepherd

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, ∑ j ≠ i D ij ≤ 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 ∈ 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. and Gupta et al. 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 [Italiano 2006] 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 2005, Grandoni 2007, Fiorini 2007]. Our main theorem establishes that this conjecture is true in general graphs. This also gives the first polynomial time algorithm for the single path VPN problem. We also show that the multipath version of the conjecture is false.

Details

FOCS Conference 2007 Conference Paper

Buy-at-Bulk Network Design with Protection

  • Spyridon Antonakopoulos
  • Chandra Chekuri
  • F. Bruce Shepherd
  • Lisa Zhang 0001

We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against edge or node failures in the network. In practice, the most popular model used in high speed telecommunication networks for protection against failures, is the so-called 1+1 model. In this model, two edge or node-disjoint paths are provisioned for each demand pair. We obtain the first non-trivial approximation algorithms for buy-at-bulk network design in the 1+1 model for both edge and node-disjoint protection requirements. Our results are for the single-cable cost model, which is prevalent in optical networks. More specifically, we present a constant-factor approximation for the single-sink case, and an {\rm O}(\log ^3 n) approximation for the multi-commodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems.

Details

FOCS Conference 2006 Conference Paper

Strategic Network Formation through Peering and Service Agreements

  • Elliot Anshelevich
  • F. Bruce Shepherd
  • Gordon T. Wilfong

We introduce a game theoretic model of network formation in an effort to understand the complex system of business relationships between various Internet entities (e. g. , Autonomous Systems, enterprise networks, residential customers). This system is at the heart of Internet connectivity. In our model we are given a network topology of nodes and links where the nodes (modeling the various Internet entities) act as the players of the game, and links represent potential contracts. Nodes wish to satisfy their demands, which earn potential revenues, but nodes may have to pay (or be paid by) their neighbors for links incident to them. By incorporating some of the qualities of Internet business relationships, we hope that our model will have predictive value. Specifically, we assume that contracts are either customer-provider or peering contracts. As often occurs in practice, we also include a mechanism that penalizes nodes if they drop traffic emanating from one of their customers. For a natural objective function, we prove that the price of stability is at most 2. With respect to social welfare, however, the prices of anarchy and stability can both be unbounded, leading us to consider how much we must perturb the system to obtain good stable solutions. We thus focus on the quality of Nash equilibria achievable through centralized incentives: solutions created by an "altruistic entity" (e. g. , the government) able to increase individual payouts for successfully routing a particular demand. We show that if every payout is increased by a factor of 2, then there is a Nash equilibrium as good as the original centrally defined social optimum. We also show how to find equilibria efficiently in multicast trees. Finally, we give a characterization of Nash equilibria as flows of utility with certain constraints, which helps to visualize the structure of stable solutions and provides us with useful proof techniques.

Details

FOCS Conference 2004 Conference Paper

Edge-Disjoint Paths in Planar Graphs

  • Chandra Chekuri
  • Sanjeev Khanna
  • F. Bruce Shepherd

We study the maximum edge-disjoint paths problem (MEDP). We are given a graph G = (V, E) and a set T = {s/sub 1/t/sup 1/, s/sub 2/t/sup 2/, .. ., s/sub k/t/sup k/} of pairs of vertices: the objective is to find the maximum number of pairs in T that can be connected via edge-disjoint paths. Our main result is a poly-logarithmic approximation for MEDP on undirected planar graphs if a congestion of 2 is allowed, that is, we allow up to 2 paths to share an edge. Prior to our work, for any constant congestion, only a polynomial-factor approximation was known for planar graphs although much stronger results are known for some special cases such as grids and grid-like graphs. We note that the natural multi-commodity flow relaxation of the problem has an integrality gap of /spl Omega/(/spl radic/|V|) even on planar graphs when no congestion is allowed. Our starting point is the same relaxation and our result implies that the integrality gap shrinks to a poly-logarithmic factor once 2 paths are allowed per edge. Our result also extends to the unsplittable flow problem and the maximum integer multicommodity flow problem. A set X /spl sube/V is well-linked if for each S /spl sub/ V, |/spl delta/(S)| /spl ges/ min{|S /spl cap/ X |, |(V - S) /spl cap/ X|}. The heart of our approach is to show that in any undirected planar graph, given any matching M on a well-linked set X, we can route /spl Omega/(|M|) pairs in M with a congestion of 2. Moreover, all pairs in M can be routed with constant congestion for a sufficiently large constant. This results also yields a different proof of a theorem of Klein, Plotkin, and Rao that shows an O(1) maxflow-mincut gap for uniform multicommodity flow instances in planar graphs. The framework developed in this paper applies to general graphs as well. If a certain graph theoretic conjecture is true, it yields poly-logarithmic integrality gap for MEDP with constant congestion.

Details