9 papers
Solving Positive Linear Programs with Differential Privacy
Alina Ene, Huy Le Nguyen, Ta Duy Nguyen +1
We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of pac…
Discrepancy Minimization via Regularization
Lucas Pesenti, Adrian Vladu
We introduce a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to re-interpret several breakthr…
Quasi-Self-Concordant Optimization with Lewis Weights
Alina Ene, Ta Duy Nguyen, Adrian Vladu
In this paper, we study the problem for a quasi-self-concordant function , where are $…
Adaptive Sparsification for Linear Programming
Ãtienne Objois, Adrian Vladu
We introduce a generic framework for solving linear programs (LPs) with many constraints via adaptive sparsification. Our approach provides a principled generalization…
Improved Regression via Iteratively Reweighted Least Squares
Alina Ene, Ta Duy Nguyen, Adrian Vladu
We introduce fast algorithms for solving regression problems using the iteratively reweighted least squares (IRLS) method. Our approach achieves state-of-the-art iterati…
Fixed-Parameter Tractable Submodular Maximization over a Matroid
Shamisa Nematollahi, Adrian Vladu, Junyao Zhao
In this paper, we design fixed-parameter tractable (FPT) algorithms for (non-monotone) submodular maximization subject to a matroid constraint, where the matroid rank is treate…