2 citations · 3 across the 4 of their papers we have counts for
5 papers
Computation and Applications of Euclidean and Normed Representations of Massive Data
Max Ovsiankin
This thesis investigates Euclidean-space and -norm representations of different forms of data, with a focus on efficient algorithms for computing these representations in s…
Approximation Algorithms for -Shortest Path and -Group Steiner Tree
Yury Makarychev, Max Ovsiankin, Erasmo Tani
We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e…
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension…
The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms
Naren Sarayu Manoj, Max Ovsiankin
Given a matrix , a partitioning of into groups , an outer norm , and a collection of inner norms such that either $p…
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their…