F. Bruce Shepherd

Publication Activity (10 Years)

Years Active: 1985-2024
Publications (10 Years): 20

Top Topics

Greedy Algorithm

Multicommodity Flow

Top Venues

Publications

Mehrdad Ghadiri, Richard Santiago, F. Bruce Shepherd
A Parameterized Family of Meta-Submodular Functions. SODA (2024)
Adam D. Jozefiak, F. Bruce Shepherd
Diversity Embeddings and the Hypergraph Sparsest Cut. CoRR (2023)
Guyslain Naves, F. Bruce Shepherd, Henry Xia
Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators. Math. Program. 197 (2) (2023)
Joseph Poremba, F. Bruce Shepherd
Cut-Sufficient Directed 2-Commodity Multiflow Topologies. IPCO (2023)
Adam Jozefiak, F. Bruce Shepherd, Noah Weninger
A knapsack intersection hierarchy. Oper. Res. Lett. 51 (1) (2023)
Guyslain Naves, F. Bruce Shepherd
When Do Gomory-Hu Subtrees Exist? SIAM J. Discret. Math. 36 (3) (2022)
Adam Jozefiak, F. Bruce Shepherd, Noah Weninger
A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees. CoRR (2022)
Mehrdad Ghadiri, Richard Santiago, F. Bruce Shepherd
Beyond Submodular Maximization via One-Sided Smoothness. SODA (2021)
Loïc Seguin-Charbonneau, F. Bruce Shepherd
Maximum edge-disjoint paths in planar graphs with congestion 2. Math. Program. 188 (1) (2021)
Guyslain Naves, F. Bruce Shepherd, Henry Xia
Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators. IPCO (2021)
Guyslain Naves, F. Bruce Shepherd, Henry Xia
Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators. CoRR (2020)
Mehrdad Ghadiri, Richard Santiago, F. Bruce Shepherd
A Parameterized Family of Meta-Submodular Functions. CoRR (2020)
Coulter Beeson, F. Bruce Shepherd
The Empirical Core of the Multicommodity Flow Game Without Side Payments. CoRR (2020)
Mehrdad Ghadiri, Richard Santiago, F. Bruce Shepherd
Beyond Submodular Maximization. CoRR (2019)
Richard Santiago, F. Bruce Shepherd
Multivariate Submodular Optimization. ICML (2019)
Richard Santiago, F. Bruce Shepherd
Multi-Agent Submodular Optimization. APPROX-RANDOM (2018)
Richard Santiago, F. Bruce Shepherd
Multi-Agent Submodular Optimization. CoRR (2018)
Guyslain Naves, F. Bruce Shepherd
When Do Gomory-Hu Subtrees Exist? CoRR (2018)
F. Bruce Shepherd, Adrian R. Vetta
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems. Theory Comput. 13 (1) (2017)
Richard Santiago, F. Bruce Shepherd
Multi-Agent and Multivariate Submodular Optimization. CoRR (2016)
F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem. FOCS (2015)
F. Bruce Shepherd, Adrian Vetta
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems. CoRR (2015)
Alexandre Fréchette, F. Bruce Shepherd, Marina K. Thottan, Peter J. Winzer
Shortest Path Versus Multihub Routing in Networks With Uncertain Demand. IEEE/ACM Trans. Netw. 23 (6) (2015)
Yossi Azar, Seny Kamara, Ishai Menache, Mariana Raykova, F. Bruce Shepherd
Co-Location-Resistant Clouds. CCSW (2014)
Neil Olver, F. Bruce Shepherd
Approximability of Robust Network Design. Math. Oper. Res. 39 (2) (2014)
Yossi Azar, Seny Kamara, Ishai Menache, Mariana Raykova, F. Bruce Shepherd
Co-Location-Resistant Clouds. IACR Cryptol. ePrint Arch. 2014 (2014)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
The All-or-Nothing Multicommodity Flow Problem. SIAM J. Comput. 42 (4) (2013)
Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd
Maximum Edge-Disjoint Paths in k-Sums of Graphs. ICALP (1) (2013)
Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd
Maximum Edge-Disjoint Paths in $k$-sums of Graphs CoRR (2013)
Yossi Azar, Ilan Reuven Cohen, Seny Kamara, F. Bruce Shepherd
Tight bounds for online vector bin packing. STOC (2013)
Navin Goyal, Neil Olver, F. Bruce Shepherd
Dynamic vs Oblivious Routing in Network Design. CoRR (2013)
Alexandre Fréchette, F. Bruce Shepherd, Marina K. Thottan, Peter J. Winzer
Shortest path versus multi-hub routing in networks with uncertain demand. INFOCOM (2013)
Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel
Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory, Ser. B 103 (2) (2013)
Navin Goyal, Neil Olver, F. Bruce Shepherd
The VPN Conjecture Is True. J. ACM 60 (3) (2013)
Alexandre Fréchette, F. Bruce Shepherd, Marina Thottan, Peter J. Winzer
Shortest Path versus Multi-Hub Routing in Networks with Uncertain Demand CoRR (2013)
Navendu Jain, Ishai Menache, Joseph Naor, F. Bruce Shepherd
Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks. ICALP (2) (2012)
Elliot Anshelevich, F. Bruce Shepherd, Gordon T. Wilfong
Strategic network formation through peering and service agreements. Games Econ. Behav. 73 (1) (2011)
Loïc Seguin-Charbonneau, F. Bruce Shepherd
Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2. FOCS (2011)
Navin Goyal, Neil Olver, F. Bruce Shepherd
Dynamic vs. Oblivious Routing in Network Design. Algorithmica 61 (1) (2011)
Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang
Buy-at-Bulk Network Design with Protection. Math. Oper. Res. 36 (1) (2011)
Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel
Flow-Cut Gaps for Integer and Fractional Multiflows CoRR (2010)
Neil Olver, F. Bruce Shepherd
Approximability of Robust Network Design. SODA (2010)
Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel
Flow-Cut Gaps for Integer and Fractional Multiflows. SODA (2010)
Navin Goyal, Neil Olver, F. Bruce Shepherd
Dynamic vs. Oblivious Routing in Network Design. ESA (2009)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
A Note on Multiflows and Treewidth. Algorithmica 54 (3) (2009)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
Edge-Disjoint Paths in Planar Graphs with Constant Congestion. SIAM J. Comput. 39 (1) (2009)
Navin Goyal, Neil Olver, F. Bruce Shepherd
The vpn conjecture is true. STOC (2008)
F. Bruce Shepherd
Single-Sink Multicommodity Flow with Side Constraints. Bonn Workshop of Combinatorial Optimization (2008)
Chandra Chekuri, F. Bruce Shepherd
Approximate Integer Decompositions for Undirected Network Design Problems. SIAM J. Discret. Math. 23 (1) (2008)
Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang
Buy-at-Bulk Network Design with Protection. FOCS (2007)
Patrick Donovan, F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong
Degree-constrained network flows. STOC (2007)
Chandra Chekuri, F. Bruce Shepherd, Gianpaolo Oriolo, Maria Grazia Scutellà
Hardness of robust network design. Networks 50 (1) (2007)
F. Bruce Shepherd, Adrian Vetta
The Demand-Matching Problem. Math. Oper. Res. 32 (3) (2007)
Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd
Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3 (3) (2007)
Andrew McGregor, F. Bruce Shepherd
Island hopping and path colouring with applications to WDM network design. SODA (2007)
Elliot Anshelevich, F. Bruce Shepherd, Gordon T. Wilfong
Strategic Network Formation through Peering and Service Agreements. FOCS (2006)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. Theory Comput. 2 (7) (2006)
Chandra Chekuri, Paul Claisse, René-Jean Essiambre, Steven Fortune, Daniel C. Kilper, Wonsuck Lee, Nachi K. Nithi, Iraj Saniee, F. Bruce Shepherd, Christopher A. White, Gordon T. Wilfong, Lisa Zhang
Design tools for transparent optical networks. Bell Labs Tech. J. 11 (2) (2006)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
Edge-disjoint paths in Planar graphs with constant congestion. STOC (2006)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
Multicommodity flow, well-linked terminals, and routing problems. STOC (2005)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
The all-or-nothing multicommodity flow problem. STOC (2004)
F. Bruce Shepherd, Adrian Vetta
Lighting fibers in a dark network. IEEE J. Sel. Areas Commun. 22 (9) (2004)
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
Edge-Disjoint Paths in Planar Graphs. FOCS (2004)
Edward G. Coffman Jr., Andreas Constantinides, Dan Rubenstein, F. Bruce Shepherd, Angelos Stavrou
Content distribution for seamless transmission. SIGMETRICS Perform. Evaluation Rev. 32 (2) (2004)
C. W. Ko, F. Bruce Shepherd
Bipartite Domination and Simultaneous Matroid Covers. SIAM J. Discret. Math. 16 (4) (2003)
Graham R. Brightwell, Gianpaolo Oriolo, F. Bruce Shepherd
Reserving resilient capacity for a single commodity with upper-bound constraints. Networks 41 (2) (2003)
Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd
Multicommodity Demand Flow in a Tree. ICALP (2003)
Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67 (3) (2003)
Timothy Griffin, F. Bruce Shepherd, Gordon T. Wilfong
The stable paths problem and interdomain routing. IEEE/ACM Trans. Netw. 10 (2) (2002)
Anindya Basu, Chih-Hao Luke Ong, April Rasala, F. Bruce Shepherd, Gordon T. Wilfong
Route oscillations in I-BGP with route reflection. SIGCOMM (2002)
András Frank, F. Bruce Shepherd, Vivek Tandon, Zoltán Végh
Node-Capacitated Ring Routing. Math. Oper. Res. 27 (2) (2002)
Andrew R. Conn, F. Bruce Shepherd
Foreword. Math. Program. 91 (3) (2002)
F. Bruce Shepherd, Adrian Vetta
The Demand Matching Problem. IPCO (2002)
Matthew Andrews, F. Bruce Shepherd, Aravind Srinivasan, Peter Winkler, Francis Zane
Clustering and Server Selection using Passive Monitoring. INFOCOM (2002)
Graham R. Brightwell, Gianpaolo Oriolo, F. Bruce Shepherd
Reserving Resilient Capacity in a Network. SIAM J. Discret. Math. 14 (4) (2001)
F. Bruce Shepherd, Lisa Zhang
A cycle augmentation algorithm for minimum cost multicommodity flows on a ring. Discret. Appl. Math. 110 (2-3) (2001)
Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd
Directed network design with orientation constraints. SODA (2000)
Timothy Griffin, F. Bruce Shepherd, Gordon T. Wilfong
Policy Disputes in Path-Vector Protocols. ICNP (1999)
Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC (1999)
Kyriakos Kilakos, F. Bruce Shepherd
Face extensions in planar cubic graphs. Discret. Math. 181 (1-3) (1998)
A. M. H. Gerards, F. Bruce Shepherd
The Graphs with All Subgraphs T-Perfect. SIAM J. Discret. Math. 11 (4) (1998)
A. M. H. Gerards, F. Bruce Shepherd
Strong orientations without even directed circuits. Discret. Math. 188 (1-3) (1998)
Kyriakos Kilakos, F. Bruce Shepherd
Excluding Minors in Cubic Graphs. Comb. Probab. Comput. 5 (1996)
Kyriakos Kilakos, F. Bruce Shepherd
-graphs. J. Graph Theory 22 (3) (1996)
Bruce A. Reed, F. Bruce Shepherd
The Gallai-Younger Conjecture for Planar Graphs. Comb. 16 (4) (1996)
Tommy R. Jensen, F. Bruce Shepherd
Note on a Conjecture of Toft. Comb. 15 (3) (1995)
F. Bruce Shepherd
Applying Lehman's theorems to packing problems. Math. Program. 71 (1995)
B. Gamble, William R. Pulleyblank, Bruce A. Reed, F. Bruce Shepherd
Right angle free subsets in the plane. Graphs Comb. 11 (2) (1995)
F. Bruce Shepherd
A note on clutter partitions. Oper. Res. Lett. 15 (3) (1994)
F. Bruce Shepherd
Near-perfect matrices. Math. Program. 64 (1994)
Colin J. H. McDiarmid, Bruce A. Reed, Alexander Schrijver, F. Bruce Shepherd
Induced Circuits in Planar Graphs. J. Comb. Theory, Ser. B 60 (2) (1994)
William R. Pulleyblank, F. Bruce Shepherd
Formulations for the stable set polytope of a claw-free graph. IPCO (1993)
Colin McDiarmid, Bruce A. Reed, Alexander Schrijver, F. Bruce Shepherd
Non-Interfering Network Flows. SWAT (1992)
F. Bruce Shepherd
Hamiltonicity in claw-free graphs. J. Comb. Theory, Ser. B 53 (2) (1991)
William McCuaig, F. Bruce Shepherd
Domination in graphs with minimum degree two. J. Graph Theory 13 (6) (1989)
Ernest J. Cockayne, B. Gamble, F. Bruce Shepherd
Domination parameters for the bishops graph. Discret. Math. 58 (3) (1986)
Ernest J. Cockayne, B. Gamble, F. Bruce Shepherd
-domination number of a graph. J. Graph Theory 9 (4) (1985)