2025 "approximation algorithms" Papers
14 papers found
Approximation algorithms for combinatorial optimization with predictions
Antonios Antoniadis, Marek Elias, Adam Polak et al.
ICLR 2025posterarXiv:2411.16600
3
citations
A Single-Swap Local Search Algorithm for k-Means of Lines
Ting Liang, Xiaoliang Wu, Junyu Huang et al.
NeurIPS 2025poster
A Unified Approach to Submodular Maximization Under Noise
Kshipra Bhawalkar, Yang Cai, Zhe Feng et al.
NeurIPS 2025posterarXiv:2510.21128
Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
Yang Cao, Xiaoyu Li, Zhao Song et al.
NeurIPS 2025poster
Fair Clustering in the Sliding Window Model
Vincent Cohen-Addad, Shaofeng Jiang, Qiaoyuan Yang et al.
ICLR 2025posterarXiv:2503.05173
3
citations
Improved Algorithms for Fair Matroid Submodular Maximization
Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski
NeurIPS 2025posterarXiv:2601.09860
Improved Approximation Algorithms for $k$-Submodular Maximization via Multilinear Extension
Huanjian Zhou, Lingxiao Huang, Baoxiang Wang
ICLR 2025poster
Near-optimal Active Regression of Single-Index Models
Yi Li, Wai Ming Tai
ICLR 2025posterarXiv:2502.18213
1
citations
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
Christopher Musco, R. Teal Witter
ICLR 2025posterarXiv:2410.01917
14
citations
Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
Shihong Song, Guanlin Mo, Hu Ding
ICLR 2025posterarXiv:2411.01115
Simple and Optimal Sublinear Algorithms for Mean Estimation
Beatrice Bertolotti, Matteo Russo, Chris Schwiegelshohn et al.
NeurIPS 2025posterarXiv:2406.05254
Stable Matching with Ties: Approximation Ratios and Learning
Shiyun Lin, Simon Mauras, Nadav Merlis et al.
NeurIPS 2025posterarXiv:2411.03270
2
citations
Streaming Algorithms For $\ell_p$ Flows and $\ell_p$ Regression
Amit Chakrabarti, Jeffrey Jiang, David Woodruff et al.
ICLR 2025poster
Unifying Proportional Fairness in Centroid and Non-Centroid Clustering
Benjamin Cookson, Nisarg Shah, Ziqi Yu
NeurIPS 2025spotlightarXiv:2601.00447
1
citations