11 citations · 20 across the 7 of their papers we have counts for
9 papers
Diversity Embeddings and the Hypergraph Sparsest Cut
Adam D. Jozefiak, F. Bruce Shepherd
Good approximations have been attained for the sparsest cut problem by rounding solutions to convex relaxations via low-distortion metric embeddings. Recently, Bryant and Tupper sh…
A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees
Adam Jozefiak, F. Bruce Shepherd, Noah Weninger
We introduce a natural knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs, i.e., where…
A Parameterized Family of Meta-Submodular Functions
Mehrdad Ghadiri, Richard Santiago, Bruce Shepherd
Submodular function maximization has found a wealth of new applications in machine learning models during the past years. The related supermodular maximization models (submodular m…
When Do Gomory-Hu Subtrees Exist?
Guyslain Naves, F. Bruce Shepherd
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…
Multi-Agent Submodular Optimization
Richard Santiago, F. Bruce Shepherd
Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) , where is a given family of feasible…
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 th…
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
F. Bruce Shepherd, Adrian Vetta
We consider single-sink network flow problems. An instance consists of a capacitated graph (directed or undirected), a sink node and a set of demands that we want to send to th…
Dynamic vs Oblivious Routing in Network Design
Navin Goyal, Neil Olver, F. Bruce Shepherd
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 impac…
Shortest Path versus Multi-Hub Routing in Networks with Uncertain Demand
Alexandre Fréchette, F. Bruce Shepherd, Marina K. Thottan +1
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 th…