11 citations · 16 across the 5 of their papers we have counts for
3 papers · 1 filter
Multipass Linear Sketches for Geometric LP-Type Problems
N. Efe Çekirge, William Gay, David P. Woodruff
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinat…
Routing under Balance
Alina Ene, Gary Miller, Jakub Pachocki +1
We introduce the notion of balance for directed graphs: a weighted directed graph is -balanced if for every cut , the total weight of edges going from to $V\s…
Online Buy-at-Bulk Network Design
Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy +1
We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem in undirected and directed graphs. Our competitive…