Approximation Algorithms

Near-optimal Coresets for Robust Clustering ICLR 2023 Near Optimal Reconstruction of Spherical Harmonic Expansions NeurIPS 2023 Optimal Scoring Rules for Multi-dimensional Effort COLT 2023 Optimizing Multiple Simultaneous Objectives for Voting and Facility Location AAAI 2023 Reconstructing an Epidemic Outbreak Using Steiner Connectivity AAAI 2023 Replicable Clustering NeurIPS 2023 Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming NeurIPS 2023 Submodular Maximization under the Intersection of Matroid and Knapsack Constraints AAAI 2023 Truthful Mechanisms for Steiner Tree Problems AAAI 2023 A Differentially Private Linear-Time fPTAS for the Minimum Enclosing Ball Problem NeurIPS 2022 Dimensionality and Coordination in Voting: The Distortion of STV AAAI 2022 Efficient Submodular Optimization under Noise: Local Search is Robust NeurIPS 2022 Generalized Stochastic Matching AAAI 2022 Generic bounds on the approximation error for physics-informed (and) operator learning NeurIPS 2022 Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem COLT 2022 Learning-Augmented Algorithms for Online Linear and Semidefinite Programming NeurIPS 2022 Parameterized Approximation Algorithms for K-center Clustering and Variants AAAI 2022 Recruitment Strategies That Take a Chance NeurIPS 2022 Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers NeurIPS 2022 Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes COLT 2022 Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression COLT 2022 Approximation Algorithms for Socially Fair Clustering COLT 2021 Fairness in Influence Maximization through Randomization AAAI 2021 Fair Scheduling for Time-dependent Resources NeurIPS 2021 Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes NeurIPS 2021