11 citations · 12 across the 3 of their papers we have counts for
6 papers
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…
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…
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…