"approximation algorithms" Papers
26 papers found
Approximation algorithms for combinatorial optimization with predictions
Antonios Antoniadis, Marek Elias, Adam Polak et al.
Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
Yang Cao, Xiaoyu Li, Zhao Song et al.
Fair Clustering in the Sliding Window Model
Vincent Cohen-Addad, Shaofeng Jiang, Qiaoyuan Yang et al.
Improved Algorithms for Fair Matroid Submodular Maximization
Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski
Near-optimal Active Regression of Single-Index Models
Yi Li, Wai Ming Tai
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
Christopher Musco, R. Teal Witter
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
Stable Matching with Ties: Approximation Ratios and Learning
Shiyun Lin, Simon Mauras, Nadav Merlis et al.
Streaming Algorithms For $\ell_p$ Flows and $\ell_p$ Regression
Amit Chakrabarti, Jeffrey Jiang, David Woodruff et al.
Unifying Proportional Fairness in Centroid and Non-Centroid Clustering
Benjamin Cookson, Nisarg Shah, Ziqi Yu
A Dynamic Algorithm for Weighted Submodular Cover Problem
Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi et al.
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar
Approximate Integer Solution Counts over Linear Arithmetic Constraints
Cunjing Ge
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems
Hao Tian, Sourav Medya, Wei Ye
Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
Vicente Balmaseda, Ying Xu, Yixin Cao et al.
Consistent Submodular Maximization
PAUL DUETTING, Federico Fusco, Silvio Lattanzi et al.
Cost Minimization for Equilibrium Transition
Haoqiang Huang, Zihe Wang, Zhide Wei et al.
Dynamic Correlation Clustering in Sublinear Update Time
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori et al.
Dynamic Facility Location in High Dimensional Euclidean Spaces
Sayan Bhattacharya, Gramoz Goranci, Shaofeng Jiang et al.
Envy-Free House Allocation under Uncertain Preferences
Haris Aziz, Isaiah Iliffe, Bo Li et al.
Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs
Slobodan Mitrovic, Theodore Pan
Improved Metric Distortion via Threshold Approvals
Elliot Anshelevich, Aris Filos-Ratsikas, Christopher Jerrett et al.
Near-Linear Time Approximation Algorithms for k-means with Outliers
Junyu Huang, Qilong Feng, Ziyun Huang et al.
Optimally Improving Cooperative Learning in a Social Setting
Shahrzad Haddadan, Cheng Xin, Jie Gao
Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
Evripidis Bampis, Bruno Escoffier, Michalis Xefteris