14 citations · 51 across the 29 of their papers we have counts for
7 papers · 1 filter
Faster Exact and Approximate Algorithms for -Cut
Anupam Gupta, Euiwoong Lee, Jason Li
In the -cut problem, we are given an edge-weighted graph and an integer , and have to remove a set of edges with minimum total weight so that has at least connect…
A PTAS for -Low Rank Approximation
Frank Ban, Vijay Bhattiprolu, Karl Bringmann +3
A number of recent works have studied algorithms for entrywise -low rank approximation, namely, algorithms which given an matrix (with ), output…
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
Euiwoong Lee, Sahil Singla
Online contention resolution schemes (OCRSs) were proposed by Feldman, Svensson, and Zenklusen as a generic technique to round a fractional solution in the matroid polytope in an o…
Approximating Operator Norms via Generalized Krivine Rounding
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We consider the -Grothendieck problem, which seeks to maximize the bilinear form for an input matrix over vectors with . The…
Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li +2
We study the problem of deleting the smallest set of vertices (resp. edges) from a given graph such that the induced subgraph (resp. subgraph) belongs to so…
Inapproximability of Matrix Norms
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We study the problem of computing the norm of a matrix , defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac…